[Baekjoon] 백준 9095_1,2,3 더하기 (Java)

📝 오늘의 일기
DP는 참 어렵다. DP는 보통 점화식을 찾아내기만 하면 코드로 옮겨 구현하는 시간은 짧은 편인데, 그 점화식을 찾아내는 방법이 연습 말고는 없는 것 같다.. 그래서 다른 알고리즘 문제풀이는 따로 포스팅을 하지 않는 편인데, DP는 잘할 때까지 포스팅하면서 정리해야 할 것 같다.

9095번: 1, 2, 3 더하기

 

문제 풀이

처음엔 DP 테이블을 2차원을 구성해서, 1로만 해당 숫자를 구성하는 경우, 1과 2로 구성하는 경우, 1,2,3으로 구성하는 경우의 수를 따져 보았는데, 2차원 배열 안에선 아무리 봐도 규칙을 찾을 수 없었다. 1차원 배열로 DP 테이블을 다시 구성해서 보니 규칙이 보였다.

위의 사진처럼 1, 2, 3으로 해당 숫자를 구성할 수 있는 경우의 수를 모두 적어가며 가지수를 구해봤다. 위의 표에서 찾은 규칙은 i 의 경우의 수는 i-1, i-2, i-3 번째 경우의 수를 모두 더한 수와 같았다. 이를 바탕으로 점화식을 아래와 같이 세울 수 있다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

 

보통 점화식을 세우는 과정이나 혹은 규칙을 찾아서 세운 후에 해당 식이 의미하는 바에 대해 생각해 보는 편인데, 위의 점화식은 다음과 같은 의미를 나타낸다.

위의 그림처럼 i-1의 모든 경우에 +1을 해준 경우들이 i번째 경우에 그대로 있는 것을 볼 수 있다. 따라서 i-1, i-2, i-3의 각 경우에 +1, +2, +3을 해서 그대로 가져오기 때문에 i-1, i-2, i-3의 경우의 수를 더한 것이 i번째의 경우의 수가 된다.

예를 들어 5의 경우의 수는 아래와 같이 구성된다.
4 + 1 로 표현 가능 → dp[4] 의 경우의 수
3 + 2 로 표현 가능 → dp[3] 의 경우의 수
2 + 3 로 표현 가능 → dp[2] 의 경우의 수

 

소스 코드 

dp 테이블의 1번째, 2번째, 3번째 값을 초기화해준 뒤, 인덱스 3부터 반복문을 통해 dp테이블 값을 채워줬다.

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));
        StringBuilder sb = new StringBuilder();
        int TC = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i = 4 ; i <= 10 ; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        for(int t = 0 ; t < TC ; t++){
            int num = Integer.parseInt(br.readLine());
            sb.append(dp[num]).append("\n");
        }
        System.out.print(sb);
    }
}