다이나믹 프로그래밍(DP) : 백준 9095 자바(Java) 1, 2, 3 더하기

문제: https://www.acmicpc.net/problem/9095

 

풀이:

규칙을 파악하고 모든 경우에 대해 계산한 값을 dp배열에 저장하고 입력받은 케이스를 출력하는 방식으로 풀었다. 규칙은 간단했다.

 

정수 1 1가지

정수 2 2가지

정수 3 3가지

정수 4 7가지

.

.

.

이렇게 내려가는데, 정수 4 = 정수 1 + 정수 2 + 정수 3 = 7가지 임을 알 수 있다.

이 규칙에 따라 dp 배열에 저장해주면 된다.

 

정답:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] dp;
    static int[] arr;
    static int n;

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

        n = Integer.parseInt(br.readLine());
        arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        dp = new int[11];

        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        doDp();

        for (int i = 0; i < n; i++) {
            System.out.println(dp[arr[i]]);
        }
    }

    public static void doDp() {
        for (int i = 3; i < 11; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
    }

}