[JAVA] 백준 알고리즘 11726번 (2xn 타일링)

문제

---

이번에 다뤄볼 문제는 11726번 문제 '2xn 타일링'입니다.

2xn 타일링 문제에서 연습해야 하는 key-point는 DP입니다.

 

DP(Dynamic Programing)는 이름때문에 어려워 하시는 분들이 많습니다.

DP는 쉽게 말하면 어려운 또는 커다란 문제를 작은 문제들로 나눠서 풀이하겠다 인데요.

작은 문제들을 해결해서 메모해놓고 나중에 더 큰 문제를 해결하면서 같은 작은 문제를 만난다면

앞서 풀었던 작은 문제의 결과를 활용하는 방식입니다.

 

해당 문제에서 주어진 큰 문제는 2xn 사이즈의 직사각형이며

이를 작은 직사각형인 2x1과 1x2 타일로 채워나가는 문제입니다.

목적지인 n까지 반복문을 수행하며 계속해서 이전에 해결한 작은문제들을 더해가면 완성됩니다.

 

문제에서 제시한 입력의 범위 중 n의 최소값이 1이고 이 경우  2x1 타일 하나로만 채워지기 때문에

dp[0]과 dp[1]에 각각 1을 세팅합니다.

그리고 2x1 부터 2x5 정도까지 노트에 그려보면서 규칙을 찾아보면

마치 피보나치 수열과 비슷해보이는 양상을 보이게 되는데, dp[i] = dp[i - 1] + dp[i - 2] 이라는 공식을 찾을 수 있습니다.

마지막으로 주의해야 할 부분은 %10007 나머지 연산을 매 루프마다 계산을 하고 dp에 넣어주어야 합니다.

마지막까지 경우의 수를 더하기만 하고 마지막에 나머지를 구할 경우 오버플로우가 발생 할 수 있으므로

나머지 연산은 매번 수행해주도록 합니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

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[n + 1];

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] = dp[i] % 10007;
        }

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

 

11726번: 2×n 타일링