문제
풀이
- 주어진 규칙에 맞춰 정삼각형의 변의 길이를 도출하는 문제이다.
- 작은 문제부터 차근차근 큰 문제의 답을 도출하는 문제로 전형적인 다이나믹 프로그래밍 문제이다.
| N | P(N) |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 4 |
- 위 테이블에서 볼 수 있듯이 N이 4 이상인 시점부터 d[i] = d[i-2] + d[i-3] 점화식이 성립한다.
- bottom-up 방식으로 구현하였다.
코드
# https://www.acmicpc.net/problem/9461
# boj, 9461: 파도반 수열, python3
import sys
input = sys.stdin.readline # 변수 입력 속도 향상
# p(n)을 구하는 함수
def solve(n: int) -> int:
d = [0] * 101 # dp table 초기화
d[1], d[2], d[3] = 1, 1, 1
# dp bottom-up
for i in range(4, n+1):
d[i] = d[i-2] + d[i-3]
return d[n] # P(N) 반환
if __name__ == '__main__':
t = int(input()) # 테스트 케이스의 개수 t
for _ in range(t): # 각 테스트 케이스마다 P(n)을 출력한다.
n = int(input())
print(solve(n))결과
출처 & 깃허브
