[CLASS 3: DP] 백준 9095 1, 2, 3 더하기

9095번: 1, 2, 3 더하기

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

 

# 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = 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 j = 0; j < t; j++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }
        System.out.print(sb);
    }
}

• 우선 1, 2, 3을 만들 수 있는 경우의 수는 다음과 같다.
  • 1 = {1} ----- 1개
  • 2 = {1+1, 2} ----- 2개
  • 3 = {1+1+1, 1+2, 2+1, 3} ----- 4개
• 그렇다면 4는 어떻게 만들 수 있을까? 고정된 수 세 개를 이용해 우선 4를 만들어 보려 한다면 4= 1+3 / 2+2 / 3+1이 된다. 즉 1, 2, 3의 각 경우의 수에 +1, +2, +3을 해주기만 하면 4를 만들 수가 있는 것이다. 각 경우의 수에 1, 2, 3만을 더해주므로 전체적인 경우의 수는 변합이 없게 되고 결과적으로 4 + 2 + 1로 7개라는 경우의 수가 발생한다.
• 또 5를 예로 들어 보면 5 = 1+4 / 2+3 / 3+2로 5를 만들 수 있다. 즉 4의 경우의 수에 +1, 3의 경우의 수에 +2, 2의 경우의 수에 +3만 해주면 5를 만들 수 있다. 최종적으로 5의 경우의 수는 7 + 4 + 2로 13이 된다.
• 이를 통해 점화식을 유추해보면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이라는 식을 세울 수 있다.

 

풀이는 아래 블로그를 참고했다.

[백준,BOJ 9095] 1, 2, 3 더하기( JAVA 구현)