백준 11726 2xn 타일링 Java

문제를 잘 읽고 푸는 방법을 생각하는 연습을 좀 해야겠다.

마지막에 어떤 수가 올 수 있는지 생각하는 것이 중요하다는 걸 깨달았다.

 

이문제 같은 경우에는 마지막이 항상 세로 타일 1개 또는 가로 타일 2개가 올 수 있다.

세로 타일이 왔을 경우는 세로 타일의 길이를 제외하면 n-1,

가로 타일이 왔을 경우는 가로 타일의 길이를 제외하면 n-2 이다.

 

마지막에 올 수 있는 타일의 형태에 따라 앞의 n-1 또는 n-2의 타일의 경우의 수는 

앞에 구해놓은 dp에서 가져오면 된다.

따라서 점화식을 dp[n] = dp[n-1] + dp[n-2] 로 만들 수 있다.

 

참 이해하기 힘든 것 같다.

 

출력은 10,007을 나머지 한 값을 출력하면 되는데

dp를 구해놓고 마지막 출력할때 %연산을 해주면 어김없이 '틀렸습니다.'로 채점된다.

이유는 dp에 넣어주는 과정에서 오버플로우가 발생한다고 한다.

그래서 dp[i]에 값을 넣어줄 때 %연산을 해줘야 정답으로 인정된다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [] dp = new int[n+1];
        
        dp[1] = 1;
        if(n>=2)
            dp[2] = 2;
 
        for(int i=3; i<=n; i++) 
            dp[i] = (dp[i-1]+dp[i-2]) % 10007 ;
        
        System.out.println(dp[n]);
    }