[Python] 백준 9461번(파도반 수열) 문제 풀이

 

p = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
for i in range(9, 100):
    p.append(p[-1]+p[-5])
for i in range(int(input())):
    print(p[int(input())-1])

 

 파도반 수열은 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410, 5842, 7739, 10252, 13581, 17991, 23833, 31572, 41824, 55405, 73396, 97229, 128801, 170625, 226030, 299426, 396655, 525456, 696081, 922111, 1221537, 1618192, 2143648, 2839729, 3761840, 4983377, 6601569, 8745217, 11584946, 15346786, 20330163, 26931732, 35676949, 47261895, 62608681, 82938844, 109870576, 145547525, 192809420, 255418101, 338356945, 448227521, 593775046, 786584466, 1042002567, 1380359512, 1828587033, 2422362079, 3208946545, 4250949112, 5631308624, 7459895657, 9882257736, 13091204281, 17342153393, 22973462017, 30433357674, 40315615410, 53406819691, 70748973084, 93722435101, 124155792775, 164471408185, 217878227876, 288627200960, 382349636061, 506505428836, 670976837021, 888855064897, 1177482265857, ... 인 수열이다.

 

 파도반 수열의 규칙은 피보나치 수열과 거의 같은데, n번째 수는 (n-1)번째 수와와 (n-4)번째 수의 합이라는 것이다. 이 규칙대로 1~100까지 수열을 담은 리스트를 만들어 준 후에, 거기서 n번째 요소를 뽑아오는 코드이다.

 

 아, 물론 n이 100보다 작거나 같으니 이렇게 풀어도 된다.

 

for i in range(int(input())):
    print([1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410, 5842, 7739, 10252, 13581, 17991, 23833, 31572, 41824, 55405, 73396, 97229, 128801, 170625, 226030, 299426, 396655, 525456, 696081, 922111, 1221537, 1618192, 2143648, 2839729, 3761840, 4983377, 6601569, 8745217, 11584946, 15346786, 20330163, 26931732, 35676949, 47261895, 62608681, 82938844, 109870576, 145547525, 192809420, 255418101, 338356945, 448227521, 593775046, 786584466, 1042002567, 1380359512, 1828587033, 2422362079, 3208946545, 4250949112, 5631308624, 7459895657, 9882257736, 13091204281, 17342153393, 22973462017, 30433357674, 40315615410, 53406819691, 70748973084, 93722435101, 124155792775, 164471408185, 217878227876, 288627200960, 382349636061, 506505428836, 670976837021, 888855064897, 1177482265857][int(input())-1])

 

 예전에 10870번 문제를 풀었던 기억이...

 

 뭐 그리고 내 블로그니까 살아가는 얘기 좀 하자면, 사실 오늘은 시험 2일차이다. 시험 2일차에 왜 PS를 하고 있냐고 묻는다면, 이번 시험은 전체 100점을 맞는 것이 목표였는데(중학생이다), 오늘 수학에서 서술형 하나를 틀렸다(...). 그래서 우울해져서 머리나 식힐 겸 백준을 풀고 있는 것이다. 내일하고 내일모레 보는 과목들은 100점 맞아야 하니 백준 좀만 풀다 공부해야지.