1. 문제와 예제
(문제링크: https://www.acmicpc.net/problem/9461)
2. 전체 코드
import sys
input = sys.stdin.readline
# 입력 받기
T = int(input().rstrip()) # 테스트 케이스 수
lst = [0, 1, 1, 1, 2, 2] # P(N) 리스트
cnt = 5 # (리스트 길이) - 1
for _ in range(T):
N = int(input().rstrip()) # P(N)의 N
while (N > cnt):
lst.append(lst[cnt] + lst[cnt-4])
cnt += 1
# 결과 출력하기
print(lst[N])
3. 코드 해설
다이나믹 프로그래밍을 활용해야 하는 문제다. 즉, P(N)의 규칙을 찾아 점화식을 풀듯이 구하면 된다.
우선 리스트의 1부터 5까지는 규칙이 없이 나오는 수이므로 미리 집어넣어 주고 (lst[N]이 P(N)을 나타내도록 lst[0]=0을 추가했다) 그 뒤의 P(N) 리스트 값은 필요하면 구해내는 방식을 사용하였다.
'백준' 카테고리의 다른 글
[백준] 11726번 파이썬 (2xn 타일링) (0) | 2024.03.31 |
---|---|
[백준] 11659번 파이썬 (구간 합 구하기 4) (0) | 2024.03.31 |
[백준] 9375번 파이썬 (패션왕 신해빈) (0) | 2024.03.29 |
[백준] 9095번 파이썬 (1, 2, 3 더하기) (0) | 2024.03.24 |
[백준] 1003번 파이썬 (피보나치 함수) (0) | 2024.03.23 |