[JAVA] 백준 (실버3) 11726번 2×n 타일링

링크

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

---

문제 설명

(정답률 36.467%)
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

---

입력 예제

2

---

출력 예제

2

---

정답 코드

1. n이 4일 때까지 직접 구해보면
   dp[1] = 1
   dp[2] = 2
   dp[3] = 5
   dp[4] = 7
   이 나온다.
   점화식을 구해보면 dp[n] = dp[n-1] + dp[n-2] 이 되고,
   재귀 함수를 이용해 풀이한다.

import java.io.*;

public class Main {

    static Integer[] dp;	//메모이제이션 배열

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        dp = new Integer[n + 1];

        System.out.println(recur(n));
    }
    
	//재귀 메소드
    static int recur(int x) {
		//배열의 원소가 null일 때
        if (dp[x] == null) {
        	//x가 1일 때
            if (x == 1) {
                dp[x] = x;
            }
            //x가 2일 때
            else if (x == 2) {
                dp[x] = x;
            } 
            //x가 1와 2가 아닐 때
            else {
                dp[x] = (recur(x - 1) + recur(x - 2)) % 10007;
            }
        }
        return dp[x];
    }
}

---

정리

동적 계획법(DP; Dynamic Programming) 문제이다.
이전에 푼 1로 만들기를 바탕으로 풀었다.
처음에는 recur 메소드에 바깥 if문을 빼고 풀어서 시간초과가 났는데
메모이제이션 배열을 쓰는 이유를 망각했다. 중복되는 연산을 줄이기 위해서 dp[x] == null은 꼭 필요하다.
그리고 main메소드에서 초기값으로 dp[1] == 1, dp[2] == 2을 할당도 해봤는데
ArrayIndexOutOfBoundsException 예외가 터졌다.
왜그런지 했다가 애초에 배열의 크기를 n+1 설정하여 n=1일 때 dp[2]==2에서 예외가 터진다.
이럴땐 애초에 배열의 크기를 입력값의 최대로 설정해주면 된다.