(Java) 백준 11726 - 2xn 타일링

문제를 보고 전형적인 DP 문제라고 생각했다.

점화식은 DP[n] = DP[n-1] + DP[n-2]로 조금만 생각해보면

금방 나오는 간단한 문제다.

이 문제를 풀면서 느꼈던것은 입력값이 최소인 1인 경우

평소 하던것처럼 배열을 n+1만 생성하면 dp[2]가 들어갈 공간이 없어서

ArrayIndexOutOfBounds가 난다는것과

메서드를 리턴 받고 나중에 10007로 나눈다면 입력값이 1000일 때

바로 오버플로우 문제가 일어나기 때문에 dp배열에 값을 저장할 때마다

10007로 나눠서 저장해야 한다는 점이다.

두 가지를 생각하지 못해 제출을 8번이나 했다.

 

---

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(bottomUp(n));
    }
    public static int bottomUp(int num) {
        // 입력값이 1일 경우를 대비해서 배열 생성
        int[] dp = new int[num + 2];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < num + 1; i++) {
            // 오버플로우 방지를 위해
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        return dp[num];
    }
}