9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 각 숫자들의 규칙성을 찾는 게 가장 중요한 문제였습니다. 한번 규칙을 파악하고 나면 쉽게 해결할 수 있는 다이내믹 프로그래밍 유형의 문제입니다.
1 = 1, 즉 1가지
2 = 1 + 1,
2, 즉 2가지
3 = 1 + 1 + 1,
1 + 2, 2 + 1,
3 즉 4가지
4 = 1 + 1 + 1+ 1,
1 + 1 + 2, 1 + 2 + 1, 2 + 1+ 1,
1 + 3, 3 + 1,
2 + 2 즉 7가지
5 = 1 + 1 + 1 + 1 + 1,
1 + 1 + 1 + 2, 1 + 1 + 2 + 1, 1 + 2 + 1 + 1, 2 + 1 + 1 + 1,
1 + 2 + 2, 2 + 1 + 2, 2 + 2 + 1
1 + 1 + 3, 1 + 3 + 1, 3 + 1 +1
2 + 3,
3 + 2 즉 13가지
6 = 1 + 1 + 1 + 1 + 1 + 1,
1 + 1+ 2 + 2, 1 + 2 + 1+ 2, 1 + 2 + 2 + 1, 2 + 1 + 1 + 2, 2 + 1 + 2 + 1, 2 + 2 + 1 + 1,
1 + 1 + 1 + 1 + 2, 1 + 1+ 1+ 2 + 1, 1 + 1 + 2 + 1 + 1, 1 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 3, 1 + 1 + 3 + 1, 1 + 3 + 1 + 1, 3 + 1 + 1 + 1
1 + 2 + 3, 1 + 3 + 2, 2 + 1 + 3, 2 + 3 +1, 3 + 1 + 2, 3 + 2 + 1,
2 + 2 + 2,
3 + 3 즉 24가지
이를 표로 정리하면 다음과 같습니다. (예시에서 나온 7과 10의 경우도 포함시킴)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 4 | 7 | 13 | 24 | 44 | 274 |
따라서 우리는 n번째 값은 n-1번째 + n-2번째 + n-3번째 값을 더한것임을 알 수 있습니다. (단 n >= 4)
소스코드
1 2 3 4 5 6 7 8 9 | dp = [0] * (12) # n이 11까지 이므로 12번째 까지 리스트를 생성한 후 0으로 초기화 dp[1] = 1; dp[2] = 2; dp[3] = 4 # for i in range(4, 12): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] tc = int(input()) for i in range(tc): n = int(input()) print(dp[n]) | cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 13460: 구슬 탈출 2 (Python) (1) | 2021.02.19 |
|---|---|
| 백준 알고리즘 9012: 괄호 (Python) (0) | 2021.02.06 |
| 백준 알고리즘 2468: 안전 영역(Python) (2) | 2021.02.05 |
| 백준 알고리즘 11724: 연결 요소의 개수(Python) (0) | 2021.02.05 |
| 백준 알고리즘 1012: 유기농 배추(Python) (0) | 2021.02.05 |