9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
문제
정수 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보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
코드
dp = [0, 1, 2, 4]
for i in range(4, 11):
dp.append(dp[i-1] + dp[i-2] + dp[i-3])
for _ in range(int(input())):
print(dp[int(input())])
- 1을 만들 수 있는 경우의 수는 1
- 2를 만들 수 있는 경우의 수는 2
1+1
2 - 3을 만들 수 있는 경우의 수는 4
1+1+1
1+2
2+1
3 - 4 이후의 수들은 `dp[:4]`에 저장된 값을 가지고 구해나가면 된다.
`i`는 `i-1`, `i-2`, `i-3`에 각각 1, 2, 3을 더하여 만들 수 있으므로 `dp[i]`의 값은 `dp[i-1] + dp[i-2] + dp[i-3]`이다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 2579번 계단 오르기 (0) | 2023.02.11 |
---|---|
[Python/파이썬] 백준 11726번 2Xn 타일링 (0) | 2023.02.10 |
[Python/파이썬] 백준 1463번 1로 만들기 (0) | 2023.02.10 |
[Python/파이썬] 백준 17626번 Four Squares (0) | 2023.02.10 |
[Python/파이썬] 백준 2839번 설탕 배달 (0) | 2023.02.09 |