====== 파도반 수열 ====== ===== 풀이 ===== * 간단한 1차원 DP. 그림을 잘 보면 P(n) = P(n-1) + P(n-6) 의 점화식을 쉽게 발견할수 있다. * 선형점화식이므로 n번째 항의 값을 O(logn)에 계산하는 것도 가능하지만, 문제에서 주어지는 n의 범위가 최대 100으로 매우 작고 여러개의 쿼리를 처리해야 하므로, 그냥 P(1)~P(n)을 O(n)에 구해두고 쿼리마다 값을 출력하는 것이 더 낫다. * [[ps:벌러캠프-매시 알고리즘]]을 공부할때 이 문제를 연습문제로 사용했었는데, 점화식의 계수가 1,0,0,0,0,1 이 아니라 1,1,0 으로 나와서 구현이 잘못된줄 알고 한참 삽질한적이 있다.. 알고보니 파도반 수열의 점화식은 P(n) = P(n-2) + P(n-3) 으로 쓰는것도 가능했다.. (사실 이게 더 일반적) * 문제와는 관계 없지만 파도반 수열에는 여러가지 특징이 있긴 하다. [[wk>Padovan sequence]] 참고. ===== 코드 ===== """Solution code for "BOJ 9461. 파도반 수열". - Problem link: https://www.acmicpc.net/problem/9461 - Solution link: http://www.teferi.net/ps/problems/boj/9461 Tags: [DP] """ def main(): T = int(input()) N = [int(input()) for _ in range(T)] dp = [None, 1, 1, 1, 2, 2] for _ in range(6, max(N) + 1): dp.append(dp[-1] + dp[-5]) for x in N: print(dp[x]) if __name__ == '__main__': main() {{tag>BOJ ps:problems:boj:실버_3}}