[056] 11726. 2xn 타일링

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

 

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

11726번: 2×n 타일링

 

---

 

 

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

 

- 직사각형 타일 1x2 와 2x1 이 채우는 방법의 수를 구하기

- 출력할 때는 10,007을 나눈 나머지를 출력

 

 

 

🧶 풀이과정

 

DP는 진짜 나는 어려워서 생각을 많이 해야 했다.

보통 이런 것은 그려보면서 생각을 하는데, 여기에서 같은 점과 계산할 수 있는 부분을 추론하면서 진행을 하게 된다.

이 문제 같은 경우에는

전까지 만들어놓은 타일에서 언제나 현재 n의 자리에서 -1과 -2의 합이 유지된다.

그러니까, -1은 세로 타일이 들어가는 만큼을 추가하는 거고, 2는 가로 타일을 추가하는 것을 생각하면 된다.

 

세로로 배치하는 타일은 1의 자리를 차지하기 때문에 n-1의 값과 같고

가로로 배치하는 타일은 2의 자리를 차지하기 때문에 n-2의 값과 같다

 

이것을 토대로 코드를 정리하면 끝

 

 

 

🏹 제출코드

 

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

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[0] = 0;
        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]);

        br.close();
     }
}