lango

찍먹? 부먹?
난 부먹 개발자.

1 minute read



문제 풀이

이 문제는 동적 계획법(DP)를 이용해 푼다면 쉽게 풀 수 있는 문제이다.


아이디어 도출

주어지는 N을 통해 순서대로 패턴을 그려보면 어떤 유형으로 1X2, 2X1의 직사각형을 채울 수 있는지 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

N = 1
2X1 직사각형 1개 필요 -> 1가지
총 1가지의 방법

N = 2
1X2 직시각형 2개 필요 -> 1가지
2X1 직사각형 2개 필요 -> 1가지
총 2가지의 방법

N = 3
1X2 직사각형 3개 필요 -> 1가지
1X2 직사각형 1개, 2X1 직사각형 1개 필요 -> 2가지
총 3가지의 방법

N = 4
1X2 직사각형 4개 필요 -> 1가지
2X1 직사각형 4개 필요 -> 1가지
1X2 직사각형 2개, 2X1 직사각형 2개 필요 -> 3가지
총 5가지의 방법

자 N을 4까지만 대입해보면 두가지의 직사각형으로 만들어낼 수 있는 가짓수의 패턴이 피보나치 수열과 동일함을 알 수 있다. N=5일 때는 당연하게도 8가지의 방법이 필요할 것이다.

그렇다면 피보나치 수열에서 N번째 수를 구하는 것과 동일한 로직으로 문제를 풀면 간단하다. 이를 위한 아이디어는 다음과 같다.

  • DP를 이용해 피보나치 수열의 N번째 수를 피보나치 함수로 구현한다.
  • DP 테이블을 별도로 두고 이미 구한 가짓수라면 바로 반환(메모이제이션)할 수 있도록 구성한다.

이때, 유의해야 할 점은 문제의 요구사항대로 방법의 수를 10,007로 나눈 나머지를 출력해야 하므로 DP 테이블에 가짓수를 갱신할 때 10,007을 나눈 나머지를 저장해야 한다.


문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import java.io.*;

class Main {    

    static int[] D;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        D = new int[N+1];

        for(int i=0; i<=N; i++) {
            D[i] = -1;
        }

        // 2*1 일때는 1가지의 방법이 있으며, 2*2일 때는 2가지의 방법이 있다.
        D[0] = 1;
        D[1] = 1;
        
        int result = fibo(N);
        
        bw.write(result+"\n");
        
        bw.close();
        br.close();
    }
    
    static int fibo(int N) {
        if(D[N] != -1) {
            return D[N];
        }
        return D[N] = (fibo(N-1) + fibo(N-2)) % 10007 ;
    }

}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy