Study/알고리즘
[백준] 9095번_1,2,3더하기
혤리
2020. 3. 11. 17:52
문제 링크 : 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보다 작다. 출력 각
www.acmicpc.net
d = [0]*11
d[1]=1;d[2]=2;d[3]=4
for _ in range(int(input())):
n = int(input())
for i in range(4,n+1):
if d[i]==0:
d[i] = d[i-1]+d[i-2]+d[i-3]
print(d[n])
아니면 좀 더 깔끔한? 점화식을 위해 d[0]=1(1,2,3을 하나도 안 쓰고 만듦->경우의 수=1)로 두고 d[1],d[2]를 초기화한 다음에 풀어도 된다.