[do it 알고리즘] 백준 11726 (동적 계획법)

동적 계획법이란?

• 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결하여
  최종적인 복잡한 문제의 답을 구하는 것

동적 계획법을 푸는 팁

1. 작은 문제로 나눌 수 있어야 하며, 점화식을 세운다.
2. DP[](다이나믹 프로그래밍) 테이블에 값을 저장한다.
3. 테이블 값을 재사용하여 시간을 단축한다. (메모이제이션 기법)
4. 바텀 - 업 (반복문) OR 탑 - 다운(재귀 함수의 형태) 방식으로 푼다.

문제 설명

 

풀기 전 생각

• 점화식을 세울 때 D[N-2], D[N-1]을 먼저 생각 (초기부터 생각하는 바텀-업 방식)
• D[1] 일 때는 세로 1개 (|) 밖에 불가능하므로 D[1] = 1
• D[2]일 때는 세로 2개 (||), 또는 가로 2개(=) 이므로 D[2] = 2
• D[3]일 때는 세로 3개(|||) 또는 가로 2개 세로 1개로 2가지 수 이므로 D[3] = 3
• D[N] = D[N-2] + D[N-1]이라는 것을 우연히 발견 (원리는 밑에서 설명)

코드

import java.util.*;
public class Baek11726 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] D = new int[N+1];
        D[1] = 1;
        D[2] = 2;
        for(int i = 3; i <= N; i++) {
            D[i] = D[i-2] + D[i-1];
        }
        System.out.println(D[N] % 10007);
    }
}

오류 및 개선

• 예제는 통과했지만 테스트 케이스 실패
• 이유는 1. 출력할 때 % 10007을 하면 int 배열인 D[i]에 값을 담을 때 int의 한계를 넘기 때문에 overflow
•             2. new int [N+1]을 하면 N = 1일 때 D[2] = 2; 로 하드코딩했기 때문에 ArrayIndexOut
• 값을 넣을 때부터 %10007을 해주며, 조건이 n <= 1000이므로 new int [1001]로 선언

최종 코드

import java.util.*;
public class Baek11726 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] D = new int[1001];
        D[1] = 1;
        D[2] = 2;
        for(int i = 3; i <= N; i++) {
            D[i] = (D[i-2] + D[i-1]) % 10007;
        }
        System.out.println(D[N]);
    }
}

강의 설명 

나의 해석

• 맨 끝에 |가 온다면, N - 1의 길이를 가진 타일의 경우의 수를 가진다.
• 맨 끝에 =가 온다면, N - 2의 길이를 가진 타일의 경우의 수를 가진다.
• 2 * N 타일의 수는 피보나치 수열이다.

DP는 코테에서 가장 자주 출제!!