[백준/JAVA] 9095번 1, 2, 3 더하기 - Dynamic Programming

문제

내용

정수 N이 주어질 경우 1,2,3의 합으로 나타내는 전체의 경우의 수를 구하는 문제이다.

주의

• 1+1+2와 2+1+1은 다른 경우이다.
• 최소 하나 이상의 수를 사용해야한다.

풀이

단순하게 dp배열을 선언한 후 숫자 3 까지 세어본 후 규칙을 찾는다.
dp[1] = 1
dp[2] = 2
dp[3] = 4
dp[4] = 7

여기서 dp[5]까지 해봤다면 매우 귀찮았을 것이다. 그래도 5까지 구하고 나면
dp[5] = 13
이 나올 것이다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
이라는 점화식이 보인다. 이를 바탕으로 7까지 세어 봤을 때 올바르게 44까지 나오게 된다.

코드

코드 설명

점화식의 시작은 4부터 시작한다.
초기값을 선언해준다.
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
이후 케이스들을 저장하고 입력값마다 출력한다.

제출 코드

import java.io.*;

class Main {

    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 T = Integer.parseInt(br.readLine());

        // 1~11
        int[] dp = new int[12];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= 11; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            bw.write(String.valueOf(dp[N]));
            bw.write("\n");
        }
        bw.flush();
    }
}