[백준] 11726 : 2xn 타일링 JAVA 풀이

N = 4일 때까지 직접 손으로 그려보니 규칙이 보여서점화식은 쉽게 도출할 수 있었다.

하지만 계속 오답처리가 됐었는데

 

그 첫 번째 이유는

배열의 크기를 N+1로 선언했는데 이때 N이 1일 경우를 고려하지 않아서였다.

점화식을 사용하기 위해 dp[1]일 때와 dp[2]일 때를 초기화해줬는데, 이러면 문제가 발생해서 애초에 배열의 크기를 N의 범위+1인 1001로 바꿔주니 해결됐다.

 

두 번째 이유는 점화식을 계산할 때 int나 long이 담을 수 있는 범위를 넘어가기 때문이었다.

따라서 경우의 수를 구하는 그 순간에 모듈러 10007을 해줘야 정확한 값이 구해진다.

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());
        int[] dp = new int[1001];
        
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i=3;i<=N;i++){
            dp[i] = dp[i-1]+dp[i-2]%10007;
        }
        System.out.println(dp[N]);
    }
}