[Java] 백준 11726 - 2×n 타일링

문제

 

풀이

이 문제는 동적 계획법을 이용하여 풀었다. 이유는 2x1, 2x2를 이용하여 더 큰 타일의 경우의 수를 생각할 수 있다고 생각했고 최적 부분 구조로 바텀업 방식을 이용해서 풀 수 있을 거라고 생각했다. 우선 점화식을 세워보기 위해 직접 그려봤는데

이러한 경우의 수가 나왔다. 1,2,3,5 순으로 늘어나며 피보나치 수를 구하는 것과 비슷하다는 생각이 들었다 2x5는 직접 그려보면 알 수 있듯이 8개가 나온다. 이 결과를 갖고 점화식을 세워 보면 dp [n]=dp [n−1]+dp [n−2]라는 식을 세워 볼 수 있고 이 식으로 구현하여 문제를 풀 수 있었다.

 

import java.io.*;


class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());
        int[] ints = new int[number+2];
        ints[1]=1;
        ints[2]=2;
        for (int i = 3; i <=number; i++) {
            ints[i]=(ints[i-1]+ints[i-2])%10007;
        }
        System.out.println(ints[number]);
    }
}

여기서 주의 해야할 점은 입력 범위를 보면 number에 1부터 들어올 수 있다. 배열을 설정할 때 number+2가 아닌 +1만 해주게 된다면 number가 1을 입력받았을때 ints [2] = 2; 부분에서 ArrayIndexOutOfBounds 오류가 발생할 수 있다는 점과 문제의 출력 부분을 보게 되면 10,007로 나눈 값을 출력하게 되어있다. 이 부분에서 만약에 출력 부분에서 10,007로 나누는 게 아닌 배열에 저장할 때 10,007로 나눈 값을 넣어줘야 한다는 걸 주의하면 좋을 거 같다.