백준 15989: 1, 2, 3 더하기 4 - DP(파이썬)

1, 2, 3 더하기 4 성공

15989번: 1, 2, 3 더하기 4

 

 

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

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

입력

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

출력

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

 

내 코드

import sys
t=int(sys.stdin.readline())

arr=[]
for _ in range(t):
    arr.append(int(sys.stdin.readline()))

#입력 받은 수 중 가장 큰 수+1개만큼 생성(인덱스 접근 편하게)
limit=max(arr)
answer=[1]*(limit+1) #적어도 1가지 이상이다.(모두 1로 더하는 경우)

#특정 수에서 마지막에 2를 더하는 경우의 수를 더함
for i in range(2,limit+1):
    answer[i] += answer[i - 2]

#특정 수에서 마지막에 3을 더하는 경우의 수를 더함
for i in range(3,limit+1):
    answer[i] += answer[i - 3]

for num in arr:
    print(answer[num])

 

풀이 및 접근)

- 이와 비슷한 문제를 푼 적이 있는데, 그 풀이에 사로잡혀서인지 해법이 계속 떠오르지 않았다.

- 해법은, 먼저 모든 수에 대한 경우의 수를 1로만 합을 구성했을 때의 케이스로 이를 한가지로 세팅한다.

- 그리고 이 상태에서 마지막에 2를 더한 경우를 추가한다. 이는 반복문으로 처음부터 끝까지 돌리면, 점차 누적되어서 알맞게 세팅된다.

- 3의 경우도 위와 같이 작성한다.

- 여기서, 2와 관련된 반복문과 3과 관련된 반복문의 위치를 바꾸어도 동일한 결과를 얻을 수 있다. 왜냐하면, 두 경우가 서로 독립적으로 일어나기 때문이다.

- 이 문제는 유독 해법을 떠올리기 어려운 문제였다.