[JAVA] 알고리즘 - 동적계획법(DP, Dynamic Programming) 백준 11726번 2xn 타일링

이제서야 동적계획법으로 문제 푸는 걸 조금씩 이해하기 시작하는 중이다.. 3일만에.... 😥

재귀도 할 때 마다 버벅거리고 너무 어려운 나라서 동적계획법을 내 머리로 직접 생각하고 구현하는데 까지 시간이 많이 소요 되었다.

 

동적 계획법 쉬운 문제들 부터 풀고 있는 중이라 아직은 혼자서 해결할 만 하다.

 

❓ 문제

11726번: 2×n 타일링

 

 

💻 테스트 케이스

예제 입력 1 

2

예제 출력 1

2

예제 입력2

9

예제 출력2

55

 

💬 문제 해결과정

여러 동적 계획법 문제를 풀다보니 초반의 규칙성을 찾는 것이 중요하다 생각하였다. 큰 문제를 작은 문제로 나누어서 해결할 수 있는지 쪼개서 해결하고 이 중복되는 규칙성을 통해 문제를 해결할 수 있기 때문에 이를 파악하는 것이 빠르게 되어야 한다.

1) 나는 우선 시작 단위인 2x1부터 이를 찾아보았다. 주어진 사각형은 (2,1) (1,2) 크기이기에 2x1을 만들 수 있는 경우의 수는 1이다.

2) 2x2에서는 (2,1), (2,1) 그리고 (1,2), (1,2) 크기의 사각형으로 2x2 크기의 사각형을 만들 수 있다. 따라서 경우의 수는 2 이다. 

3) 2x3에서는 (2,1), (2,1), (2,1) / (2,1), (1,2), (1,2)  / (1,2), (1,2) ,(2,1) 로 3가지의 경우의 수가 나온다.

----> 여기서 부터 사실 감을 잡을 수 있다. 

4) 2x4에서는 (2,1), (2,1), (2,1), (2,1) / (2,1), (2,1), (1,2), (1,2) / (2,1), (1,2), (1,2), (2,1) / (1,2), (1,2), (2,1), (2,1) / (1,2), (1,2), (1,2), (1,2) 총 5가지의 경우의 수가 나온다. 

 

즉, (n-1 경우의 수) + (n-2 경우의 수) = n의 경우의 수인 것이다. 

 

 이전의 경우의 수를 메모이제이션 하고 규칙을 따라 코드를 구성해주면 다음과 같다.

 

import java.io.*;
import java.util.*;

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[] bp = new int[N+1];
        
        bp[1] = 1;
        if(N >= 2) {
            bp[2] = 2;
        }
        
        for(int i = 3 ; i <= N ; i++) {
            bp[i] = (bp[i-2] + bp[i-1])%10007;
        }
        
        System.out.println(bp[N]);
    }
}

 

🧐 헤맸던 부분

처음에 실패했던 부분이 있는데 System.out.println 에서 바로 bp[N] % 10007 을 해주었을 때 였다. 테스트 케이스를 아무리 적용해봐도 답은 동일하게 나오는데 뭐가 문제인지 파악하지 못하고 있었다. 문제는 이전의 값에도 10007 의 나머지를 적용하는지 안 하는지에 따라 달라지는 것이었고 이전의 값에도 10007의 나머지를 적용하는 것으로 코드를 변경해주니 쉽게 통과할 수 있었다.