[백준 9095번] 1,2,3 더하기 - (Java/python)

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

9095번: 1, 2, 3 더하기

 

Idea

정수 n을 1,2,3 의 합으로 나타내는 방법의 수를 구하는 문제이다. n은 1,2,3 을 사용해서만 나타낼 수 있다.

? + .... + ? + ? + ? = n 이라고 할때 모든 ?에는 1,2,3 중 하나가 들어간다.

일단 마지막 ? 만 본다고 하면 마찬가지로 1,2,3중 하나가 들어갈 것이다. 

? + .... + ? + ? + 1 = n

? + .... + ? + ? + 2 = n

? + .... + ? + ? + 3 = n

그러면 우리는 이걸 더 작은 문제로 바꿔서 생각 해볼 수 있다. 

? + .... + ? + ?  = n -1  

? + .... + ? + ?  = n -2

? + .... + ? + ?  = n -3

n-1 도 마찬가지로 마지막 ? 에 1,2,3 중 하나가 올 수 있다. n-2 , n-3 도 마지막 ? 에 1,2,3 중 하나가 올 수 있다. 

d[n] 을 정수 n 을 1,2,3 의 합으로 나타내는 방법의 수라고 하면 

d[n] = d[n-1] + d[n-2] + d[n-3] 이라고 나타 낼 수 있고 d[n-1] 또한 d [n-1-1] + d[n-1-2] + d[n-1-3] 으로 나타 낼 수 있다.

 큰 문제를 구하는데 작은 문제의 답을 사용한다는 것을 알 수 있다. dp 방식으로 문제를 해결 할 수 있다.

 

dp 는 가장 작은 문제에 대한 답을 구해서 저장하는게 중요하다. 

d[1] 은 1 을 1,2,3 의 합으로 나타내는 방법의 수 이므로 1 하나만 존재한다.

d[2] 는 1+1 , 2 2개가 존재한다.

d[3] 은 1+2, 1+1+1, 2+1, 3  4개가 존재한다. 

 

주어질수 있는 n 값은 최대 11이므로 숫자가 매우 작기 때문에 매번 n 크기만큼 배열을 선언하지 않고 크기가 11인 최대 배열을 만들고 풀었다.  

풀이

Java

import java.util.Scanner;

/**
 *  1,2,3 더하기 (9095번)
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // 반복할 횟수 입력

        for(int k=0; k<t; k++){
            int n = sc.nextInt(); // 정수 입력
            int[] d = new int[11];
            d[1] = 1;
            d[2] = 2;
            d[3] = 4;
            for(int i=4; i<=n; i++){
                d[i] = d[i-1] + d[i-2] + d[i-3];
            }
            System.out.println(d[n]);
        }
    }
}

 

 

Python

t = int(input())


for _ in range(t):
    n = int(input())
    d = [0]*12
    d[1] = 1
    d[2] = 2
    d[3] = 4
    for i in range(4,n+1):
        d[i] = d[i-1]+d[i-2]+d[i-3]
        
    print(d[n])