[알고리즘] 백준 9095 1, 2, 3 더하기 -DP- 자바

 

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

백준 DP 유형의 문제를 풀어봤습니다. DP 유형은 이번년도에는 처음 푼 것 같네요..

역시 생각하는거나 규칙성을 찾는게 어려운 것 같습니다. ㅠ_ㅠ

 

1,2,3 으로 해당 숫자를 만들 수 있는 경우의 수를 찾는 문제 입니다. 

 

1,2,3 의 덧셈으로 이루어진 경우의 수 이므로

1 일때 경우의 수  (1) - 1가지

2 일때 경우의 수  (1+1, 2) - 2가지

3 일때 경우의 수  (1+1+1, 1+2, 3) - 4가지

4 일때 경우의 수 (1+1의 총케이스, 2+2의 총케이스, 3+3의 총케이스) - 7가지

로

 

다음과 같은 점화식을 얻을 수 있습니다.

N의 경우의 수 = nums[N - 1] + nums[N - 2] + nums[N - 3];

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[] nums = new int[11]; // n은 양수이며 11보다 작다
        nums[1] = 1; // (1) - 1가지
        nums[2] = 2; // (1+1, 2) - 2가지
        nums[3] = 4; // (1+1+1, 1+2, 3) - 4가지
        // nums[4] -> (1+1의 총케이스, 2+2의 총케이스, 3+3의 총케이스) = 7
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            for (int j = 4; j <= n; j++) {
                nums[j] = nums[j - 1] + nums[j - 2] + nums[j - 3];
            }
            System.out.println(nums[n]);
        }
    }
}

 

 

github.com/mtjin/algorithm_practice/blob/master/%EB%B0%B1%EC%A4%80%209095%201%2C%202%2C%203%20%EB%8D%94%ED%95%98%EA%B8%B0%20-dp-/Main.java

mtjin/algorithm_practice

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!