백준 11727 - 2×n 타일링2 [DP/JAVA]

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

 

11726 2×n 타일링 문제에 이어진 문제이다. 

11726번과 달라진 점은 1×2, 2×1에 2×2타일이 추가되었다는 것이다. 

---

사고방식

아주 비슷한 문제이다. 11726과 똑같이 풀되 가로로 길게 놓인 1×2 타일이 위아래로 2개 놓이는 경우에 대해 2×2 타일 1개가 놓일 수 있는 경우를 추가로 계산해주면 된다. 

따라서 11726 점화식 dp[n] = dp[n-1] + dp[n-2]에서 dp[n-2] 항을 한번 더 더해주면 된다.

(가장 마음 편한 방법은 역시 1부터 10정도까지 직접 넣어보며 값을 구하고 규칙 찾아서 점화식 찾는 방법이다.)

---

결론

점화식 : dp[n] = dp[n-1] + dp[n-2]*2

import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int dp[] = new int [1001];
        dp[1]=1;
        dp[2]=3;
        
        for(int i=3; i<n+1; i++){
            dp[i] = (dp[i-1] + dp[i-2]*2) % 10007;
        }
        System.out.println(dp[n] % 10007);
    }
}