[코딩테스트] 백준 11726 자바

백준 11726

백준 11726 문제

해당 문제는 예시로 5개의 직사각형을 이용하여 타일을 채우는 방법을 보여준다. 이는 4개의 직사각형을 이용하여 타일을 채우는 방법에서 마지막에 직사각형을 하나 더 붙인 것과 동일하다. 그리고 4개의 직사각형으로 타일을 만드는 경우의 수는 항상 고정되어 있다. 그렇다면 이 문제는 동적 계획법을 통해 해결할 수 있음을 예상해야 한다.

동적 계획법으로 해결할 수 있다고 예상이 된다면 점화식을 먼저 정의해야 한다. 우선 이 문제에서는 input이 하나밖에 없기 때문에 1차원 점화식으로 선언한다.

그리고 문제가 단순화되도록 1부터 N-1 크기의 타일을 채우는 경우의 수를 모두 구해 놓았다고 가정해야 한다.

위의 그림과 같이 N-2까지 타일이 채워져 있는 경우 중에서 세로로 타일을 채우는 경우의 수는 N-1까지 타일이 채워져 있는 경우와 중복이 되기 때문에 가로로 타일을 채워넣는 경우의 수만 더해주면 된다.

그러면 점화식을 D[N] = D[N - 1] + D[N - 2]로 도출할 수 있다.

import java.util.*;

public class Boj11726 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[1001];

        arr[1] = 1; // n = 1일 때 타일 채우는 경우의 수
        arr[2] = 2; // n = 2일 때 타일 채우는 경우의 수

        for (int i = 3; i <= n; i++) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % 10007; // 바텀-업 방식으로 점화식 사용
        }

        System.out.println(arr[n]);
    }
}

풀이

1. 최대값이 1000이고, 0번째 인덱스는 사용하지 않기 때문에 1001길이의 배열 arr을 선언한다.
2. n이 1일 때 타일을 채우는 경우의 수는 1이기 때문에 1로, n이 2 때 타일을 채우는 경우의 수는 2이기 때문에 2로 초기화해준다.
3. n이 3일 때부터는 위에서 도출한 점화식 D[N] = D[N - 1] + D[N - 2]으로 구할 수 있기 때문에 반복문을 3부터 n까지 반복하며 점화식으로 구한 값을 10007의 나머지로 배열을 채워준다.
4. 배열의 n번째 인덱스의 값을 출력한다.