[Python/백준/9095번] 1, 2, 3 더하기

출처 : www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

* 이 포스팅은 Baekjoon online judge 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의 합으로 나타내는 방법의 수를 출력한다.

입출력 예

입력	출력
3 4 7 10	7 44 274

# 설명

• 동적 프로그래밍(DP, Dynamic Programming) : 기존 결과를 활용하여 문제를 해결하는 기법

• 숫자 1, 2, 3의 합으로 정수 N을 표현하는 방법은 다음과 같은 3가지 케이스가 있다.

  • (N-1)을 숫자 1, 2, 3의 합으로 표현한 모든 경우에 1을 더하면 N이 된다.

  • (N-2)을 숫자 1, 2, 3의 합으로 표현한 모든 경우에 2를 더하면 N이 된다.

  • (N-3)을 숫자 1, 2, 3의 합으로 표현한 모든 경우에 3을 더하면 N이 된다.

• 따라서, 숫자 1, 2, 3으로 표현할 수 있는 (N-1), (N-2), (N-3)의 경우의 수를 모두 더해주면 문제가 해결된다.

 

• 먼저, 숫자 1을 1, 2, 3의 합으로 표현할 수 있는 케이스는 다음 1가지 이다.

  • 1

• 숫자 2를 1, 2, 3의 합으로 표현할 수 있는 케이스는 다음 2가지 이다.

  • 1 + 1

  • 2

• 숫자 3을 1, 2, 3의 합으로 표현할 수 있는 케이스는 다음 4가지 이다.

  • 1 + 1 + 1

  • 1 + 2

  • 2 + 1

  • 3

 

• 숫자 4를 1, 2, 3의 합으로 표현할 수 있는 케이스는 다음과 같다.

  • 1을 1, 2, 3의 합으로 표현할 수 있는 경우의 수

    • 1 + 3

  • 2를 1, 2, 3의 합으로 표현할 수 있는 경우의 수

    • 1 + 1 + 2

    • 2 + 2

  • 3을 1, 2, 3의 합으로 표현할 수 있는 경우의 수

    • 1 + 1 + 1 + 1

    • 1 + 2 + 1

    • 2 + 1 + 1

    • 3 + 1

• 따라서 총 7가지 경우의 수가 나온다.

 

• 숫자 5를 1, 2, 3의 합으로 표현할 수 있는 경우의 수는 다음과 같다.

• 숫자 2를 1, 2, 3의 합으로 표현할 수 있는 경우의 수 (각각의 경우에 수에 3만 더해주면 되므로) + 

• 숫자 3를 1, 2, 3의 합으로 표현할 수 있는 경우의 수 (각각의 경우에 수에 2만 더해주면 되므로) +

• 숫자 4를 1, 2, 3의 합으로 표현할 수 있는 경우의 수 (각각의 경우에 수에 1만 더해주면 되므로) =

• 2 + 4 + 7 = 13이다.

 

• 이를 파이썬 코드로 구현하면 다음과 같다.

for _ in range(T):
    N = int(input())
 
    cache = [1, 2, 4]
    for i in range(3, N):
        cache.append(cache[i-3] + cache[i-2] + cache[i-1])
        
    print(cache[N-1])