백준 / 123더하기 / 9095
Question
문제링크
Silver 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
Input
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
3
4
7
10
Output
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
7
44
274
Logic
기본 구조 : loop
1,2,3합을 나타내는 함수를 f(x)라 하면,
숫자 | 경우의수 | 가짓수 |
---|---|---|
1 | 1 | 1 |
2 | 1+1, 2 | 2 |
3 | 1+1+1, 2+1, 1+2, 3 | 4 |
4 | 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 3+1, 1+3 | 7 |
5 | ... | 13 |
6 | ... | 24 |
료 표현할 수 있다.
4의 경우의 수 세 가지로 나눠보면,
- 1+ 1의 경우의 수
- 2+ 2의 경우의 수
- 3+ 3의 경우의 수
이고, 세가지를 더한 1+2+4는 7임을 알 수 있다.
또한 가짓수 숫자들 목록 앞에 1을 붙이고 써보면,
1, 1, 2, 4, 7, 13, 24....인데, 이는 앞의 세 수를 더한 결과임을 알 수 있다.
따라서, f(x) = f(x-3) + f(x-2) + f(x-1)을 만족한다.
이를 반복문으로 나타내면 아래의 코드와 같다.
Code
from sys import stdin
def fibo2(n):
cur1,cur2,next = 0,0,1
for i in range(n):
cur1,cur2,next = cur2,next,cur1+cur2+next
return next
for i in range(int(stdin.readline())):
N=int(stdin.readline())
print(fibo2(N)%10007)
Author And Source
이 문제에 관하여(백준 / 123더하기 / 9095), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@swany0509/백준-123더하기-9095저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)