알고리즘

백준 9095 - 1, 2, 3 더하기 (Python)

jamie2779 2024. 2. 12. 03:32

문제

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

 

9095번: 1, 2, 3 더하기

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

www.acmicpc.net

풀이

a = [int(input()) for i in range(int(input()))]
target = max(a)
save = [1] * (target + 1)
save[1] = 1
save[2] = 2
save[3] = 4
for i in range(4,target+1):
    save[i] = save[i-1] + save[i-2] + save[i-3]

for i in a:
    print(save[i])

 

테스트케이스 만큼 입력을 받고 가장 큰 수만큼 배열을 생성하여 그 이하 숫자에 대해서 정답을 모두 구한다.

 

숫자 i 를 1, 2, 3으로 만드는 경우는 아래 3가지 중 한가지 이다. 

 

1) i-3을 만드는 각각의 경우에 +3을 하는 경우

2) i-2를 만드는 각각의 경우에 +2를 하는 경우

3) i-1를 만드는 각각의 경우에 +1 을 하는경우

 

즉 i번째 수를 만드는 경우의 수는 i-3번째, i-2번째, i-1번째 경우의 수를 더한 것과 동일하다.

이를 DP로 구현해서 입력받은 각각의 테스트케이스에 해당하는 인덱스의 값을 출력해주었다.