ALGORITHM

[백준] 1,2,3 더하기 JAVA

girin_dev 2023. 8. 7. 17:12
728x90
반응형

동적 계획법

 

백준 1,2,3 더하기 

 

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

 

9095번: 1, 2, 3 더하기

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

www.acmicpc.net

 

동적 계획법 DP 를 떠올리며 문제를 풀기는 쉽지 않다.

 

 

import java.util.Scanner;

public class 백준1_2_3더하기 {
    /*
     ex )
    3
    4
    7
    10
     */
    static int[] dp = new int[11];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        dp[1] = 1;
        dp[2] = 2;  // 점화식을 떠올리기 까지의 과정이 DP풀이의 포인트
        dp[3] = 4;  // 점화식을 세워야 한다. dp[n] = dp[n-3] + dp[n-2] + dp[n-1];

        for (int j=0; j<T; j++) {
            int N  = sc.nextInt();
            for (int i=4; i<11; i++) {
                dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
            }
            System.out.println(dp[N]);
        }

    }

}

 

320x100
반응형