백준 11727번 - 2×n 타일링 2 [브루트 포스/자바 JAVA]

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

백준 11727번

---

사고방식 

이전 포스팅인 11726번 2×n 타일링 문제에 이어진 문제이다. 

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

 

 

위 문제와 달라진 점은 1×2, 2×1에 2×2타일이 추가되었다는 점이다. 

 

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

 

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

(역시나 바로 떠오르지 않는다면 가장 확실한 방법은 1부터 10정도까지 직접 넣어보며 값을 구하고 규칙을 찾아내는 것이다. 놀랍게도 나는 이번에 제대로 된 사고 방식으로 dp[n-2]를 한번 더 더해주면 되겠구나 라는 생각이 들었다..!!!!! ) 

 

---

결론 

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);
    }
}