백준/11726번/Java - 2×n 타일링 (DP)

 

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

---

점화식을 세워서 간단하게 해결할 수 있다.

 

N = 5 인 경우 를 예를 들어 보면,

5개을 타일을 채우기 전, 4개의 타일을 채웠다고 생각해보면, 남은 칸은 1*2 한칸밖에 없어 선택지가 없다.

따라서 A[5] = A[4] + ???  임을 알 수 있다.

3개의 타일을 채웠다고 생각해보면 가로로 두개를 쌓는 방법과, 세로로 두개를 채우는 방법이 있다.

그런데 세로로 두개를 채우는 방법은 이미 A[4]에 포함되어있으므로 

A[5] = A[4] + A[3]임을 알 수 있다.

따라서 점화식은 A[i] = A[i-1] + A[i-2] 이다.

 

* 문제에서 왜 굳이 10007로 나눈 나머지를 출력하라고 하는지 의아했는데, 방법의 수가 너무 커져서 int를 초과하는 경우가 발생하는 듯 하다.

마지막에 정답을 출력할 때 배열의 값을 나누면 오류가 발생하므로 배열에 저장할 때 나누기 연산을 한 뒤 저장하여야 한다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        //점화식 arr[n] = arr[n-1] + arr[n-2]
        int[] arr = new int[1001]; // 범위를 n+1로 하면 n = 1일때 에러가 발생함 문제에서 n범위는 최대 1000
        //초기화
        arr[1] = 1;
        arr[2] = 2;
        for(int i=3; i<=n; i++) {
        	//오버플로우 방지를 위해 배열에 저장하기 전에 미리 나눠놓자.
            arr[i] = (arr[i-1] + arr[i-2]) % 10007;
        }
        System.out.println(arr[n]);




        br.close();
    }

}