[백준] 9095번 : 1, 2, 3 더하기 (동적 계획법(Dynamic) 실버Ⅲ) - Python, Java

문제

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

9095번: 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

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

예제 입력1

3
4
7
10

예제 출력 1

7
44
274

접근

이 문제의 관건은

1. 어떤 수를 1, 2, 3만을 사용해 합으로 나타내야 한다.
2. 1,2,3의 순서가 바뀌면 다른 표현이다.

이기 때문에, 우선 규칙을 찾아야 한다.

n이 4 이상일 때는 1, 2, 3을 모두 사용해 나타낼 수 있기 때문에 규칙을 찾을 수 있을 것이다.

우선 결론적으로 갯수만 나타내보면 다음과 같다.

n	갯수
1	1
2	2
3	4
4	7
5	13

n>=4 인 경우부터는 앞의 세 개 경우의 갯수를 합친 것이 답이라는 걸 볼 수 있는데,

왜 그렇게 되는지를 알아보자.

우선 4 라는 숫자는

3 + 1
2 + 2
1 + 3

으로 나타낼 수 있다. 즉 3을 나타내는 방법 + 2를 나타내는 방법 + 1을 나타내는 방법이라고 생각하면 된다.

실제로 나타낼 수 있는 합을 모두 작성해 뜯어보면

① 3 + 1 의 경우 👉 n = 3 일 때 방법의 수

② 2 + 2 의 경우 👉 n = 2 일 때 방법의 수

③ 1 + 3 의 경우 👉 n = 1 일 때 방법의 수

이처럼 해당 숫자를 나타내는 방법이 그대로 사용되는 걸 알 수 있다.

마찬가지로 n = 5 인 경우에도,

① 4 + 1 의 경우 👉 n = 4 일 때 방법의 수

② 3 + 2 의 경우 👉 n = 3 일 때 방법의 수

③ 3 + 3 의 경우 👉 n = 2 일 때 방법의 수

로 표현되는 걸 확인할 수 있다.

결국 이는 재귀적인 수식으로 나타낼 수 있으므로 점화식으로 표현할 수 있는 것이다.

f(1)=1, f(2)=2, f(3)=4 이며, 
 f(n) = f(n-1) + f(n-2) + f(n-3) (n>=4) 이다.

풀이 코드

• 따라서 코드로 구현할 때도 간단히 재귀함수를 사용하면 된다.

Python

T = int(input())


for _ in range(T):
    def Recur(num):
        if num == 1:
            return 1
        elif num ==2:
            return 2
        elif num ==3:
            return 4
        else:
            return (Recur(num-3)+Recur(num-2)+Recur(num-1))
    n = int(input())
    print(Recur(n))

Java

import java.util.Scanner;

public class Main { 
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        for (int i = 0; i<T; i++){
            int n = scanner.nextInt();
            System.out.println(Recur(n));
        }
    }
    private static int Recur(int num){
        if (num == 1) {
            return 1;
        } else if (num == 2) {
            return 2;
        } else if (num == 3) {
            return 4;
        } else {
            return (Recur(num - 3) + Recur(num - 2) + Recur(num - 1));
        }
    }
}

 

코드 자체는 간단히 구현이 가능하나, 어떤 점화식으로 나타내야하는지 로직을 구성하기 위해 고민하는 시간 때문에 풀이에 다소 시간이 걸렸던 문제이다.