[057] 11727. 2xn 타일링 2

✨ 알고리즘 분류 : 다이나믹 프로그래

 

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

11727번: 2×n 타일링 2

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 2*1 , 1*2, 2*2 타일을 2*n 크기의 직사각형으로 채운다

- 출력은 10,007을 나눈 나머지로 출력.

 

 

 

🧶 풀이과정 

 

저번에 했던 것과 유사하다.

2024.04.11 - [Algorithm] - [056] 11726. 2xn 타일링

[056] 11726. 2xn 타일링

 

여기에서 추가된 건 2*2 타일인데, 잘 생각해보면 결국 2*1 두개, 2*2 두개가 추가된 것이라고 보면 된다.

그러니까 이게 어떤 말이냐면, 저번에 풀었던 2*n 타일링에서 2*1 2*2 가 두개씩 붙어있는 타일을 두배로 추가한 값과 같다는 거다.

이 말인 즉, n-2의 타일이 두배인 것과 그 결과가 같다.

 

정리하면 다음과 같음!

 

- 2 * 2 타일이 추가되었다는 뜻은 결국 1 * 2와 2 * 2 타일이 붙어있는 것이 추가된 것과 같다.
- 그것은 결국 이전에 i - 2 에 있던 것을 추가할 때, 그것의 두배를 가져오는 것과 같음을 뜻한다.
- 그렇기 때문에 저번에 했던 점화식에서 뒤의 dp[i-2] 를  dp[i-2] * 2로 변경하면 된다.

 

 

 

🏹 제출코드

 

package data_structure_part_01;

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

public class Q11727 {

    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[0] = 0;
        dp[1] = 1;
        dp[2] = 3;

        for(int i = 3; i <= n ; i++){

            dp[i] = (dp[i-1] + (dp[i -2] * 2)) % 10007;
        }

        System.out.println(dp[n]);

        br.close();

    }
}