[BOJ] 백준 9095번 - 1, 2, 3 더하기

문제

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

9095번: 1, 2, 3 더하기

 

풀이

• 각 항들의 관계 점화식을 구하기 위해 N이 1~5일 경우를 차례대로 구해본다.

• N을 1, 2, 3의 합으로 표현하는 방법의 수
  = N-3을 1, 2, 3의 합으로 표현하는 방법의 수
  + N-2를 1, 2, 3의 합으로 표현하는 방법의 수
  + N-1를 1, 2, 3의 합으로 표현하는 방법의 수
• N-3 값에 3을 한번 더하면 N,
  N-2 값에 2를 한번 더하면 N,
  N-1 값에 1을 한번 더하면 N이기 때문에 N값은 이 세 값들을 토대로 구할 수 있다.
• dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
• dp[1], dp[2], dp[3] 의 경우, dp[0] 값에 영향을 받기 때문에 각각 1, 2, 4로 고정시켜둔다.
• dp[n] 값을 구하기 위해서는 사전에 dp[1]~dp[n-1] 까지의 값이 계산되어야 한다. => DP Bottom-Up 방식

 

코드

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        StringBuffer sb = new StringBuffer();

        for (int tc = 0; tc < testCase; tc++) {
            int n = sc.nextInt();

            int[] dp = new int[n + 3];  // n이 1일 경우 대비
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;
            for (int i = 4; i <= n; i++) {
                dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
            }

            sb.append(dp[n] + "\n");
        }

        System.out.println(sb);
    }
}

 

★ DP 문제는 역시 익숙한 패턴의 문제가 아닌 이상, 1~5 정도까지의 경우를 직접 손으로 그려보면서 점화식(각 항 사이의 관계)을 파악하는 게 최선인 것 같다.