메모리: 31256 KB, 시간: 40 ms
다이나믹 프로그래밍
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
처음 계산할 때는 그냥 점화식이 보여서 했는데, 원리를 아무리 찾아도 잘 모르겠었다. 그래서 다른 풀이를 참고했는데 dp[4]를 예시로 들자면
4는 1+3, 2+2, 3+1 꼴이므로 dp[3], dp[2], dp[1]의 결과가 모두 필요하다.
5를 예시로 든다고 해도
이므로 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이 된다.
import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * (11)
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4, 11):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
for _ in range(n):
v = int(input())
print(dp[v])