[백준_DP]9095_1,2,3 더하기

이번에 풀어볼 문제 또한 DP 를 이용한 문제입니다.

바로 보도록 하죠.

정수 N이 주어졌을 때, 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제.

이 문제는 1,2,3이라는 주어진 숫자를 통해서 힌트를 얻을 수 있습니다.

4를 예로 들어볼게요.

4는 3+1, 2+2 그리고 1+3으로도 이뤄질 수 있죠.

3을 만들 수 있는 숫자들 + 1

2를 만들 수 있는 숫자들 + 2

1을 만들 수 있는 숫자들 + 3

을 하면 4를 만들 수 있는 숫자들의 개수가 나오지 않을까?

라는 의문을 가지고 진짜 그런지 나열 해보도록 하죠.

위에 말한대로 정말 그렇군요!!

그럼 우리는 이대로 코드를 짤 수 있겠죠?

DP[N] = DP[N-1] + DP[N-2] + DP[N-3]

가 되겠습니다~

전체 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Al9095 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder build = new StringBuilder();
        
        int testCase = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 4;
 
        /* DP 값 생성 */
        for (int i = 4; i < dp.length; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        /* 문제 풀기 */
        for (int i = 0; i < testCase; i++) {
            int N = Integer.parseInt(br.readLine());
            build.append(dp[N] + "\n");
        }
        System.out.println(build.toString());
    }
}

DP에 '무엇을 저장 하느냐' 가 중요한것 같습니다.

이번 문제는 DP에 수를 만드는 개수를 저장한다.

즉 이전에 구했던 수를 만드는 개수를 재활용하는 문제였습니다.