백준 9095번: 1, 2, 3 더하기 (파이썬)

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의 합으로 나타내는 방법의 수를 출력한다.

 

풀이

 

문제를 읽고 DP로 해결해야 하는 문제라고 생각했다.

arr 리스트는 해당 인덱스를 1, 2, 3의 합으로 나타내는 방법의 수를 저장하도록 구현하였다. 1, 2, 3의 합으로 숫자를 나타내야 하기 때문에, 3까지는 직접 방법의 수를 구해 해당 값으로 초기화를 해주어야 한다. 1은 1의 한 가지 방법으로, 2는 1+1, 2의 두 가지 방법으로, 3은 1+1+1, 1+2, 2+1, 3의 4가지 방법으로 표현할 수 있다. 이제 문제에 나와있는 4의 예시를 보자. 1을 표현하는 방법 뒤에 3을 붙여 1+3의 형태로 나타낸 것 1가지, 2를 표현하는 방법 뒤에 2를 붙여 1+1+2, 2+2의 형태로 나타낸 것 2가지, 3을 표현하는 방법 뒤에 1을 붙여 1+1+1+1, 1+2+1, 2+1+1, 3+1의 형태로 나타낸 것 4가지를 포함하여 총 7가지의 방법의 수가 나온다. 이를 일반화하여 식으로 나타내면 arr[i] = arr[i-3] + arr[i-2] + arr[i-1] (단, i >= 4)이다. 문제에서 n은 양수이고 11보다 작기 때문에, 해당 범위만큼 메모이제이션하여 문제를 해결하였다.

 

소스 코드

t = int(input())

arr = [-1, 1, 2, 4]

for i in range(4, 11):
    arr.append(arr[i-3]+arr[i-2]+arr[i-1])

for _ in range(t):
    n = int(input())
    print(arr[n])