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

문제 링크

https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

정답 코드는 아래와 같습니다.

def solve():
  t = int(input())
  value = 0
  arr = []
  for _ in range(t):
    a = int(input())
    arr.append(a)
    value = max(value, a)
  rst = [1, 1, 1, 2, 2]
  for i in range(5, value):
    tmp = rst[i-1] + rst[i-5]
    rst.append(tmp)
  for i in range(t):
    print(rst[arr[i]-1])
 
solve()
 

 

이 문제는 프로그래밍 문제라기보다, 수학 문제에 더 가깝습니다. 핵심은 규칙성을 찾아내는 것입니다.

이 문제가 만일 실제 세상에서 발생한 문제라면 저도 규칙성을 찾아내기는 어려웠을 것 같습니다.

하지만 다행(?)스럽게도 이것이 문제라는 것은(출제되었다는 것은) 해답이 존재한다는 것을 의미하므로,

역으로 해답이 존재한다면 어떤 형태일 것인지를 추론하고, 문장의 의미들을 파악하여 어떠한 규칙성이 있을 것임을 예상할 수 있습니다.

문제 이름도 "수열"이고, 표현할 때에도 P(x) 형식으로 표현한다는 점 등을 고려하면, 뭔가 점화식으로 나타낼 수 있을 것같다는 생각이 들게 됩니다.

그래도 막상 어떻게 표현해야 할지 모르겠으니 실제로 각 경우들이 어떻게 구성되는지 확인하면서 식을 추론했습니다.

제가 자주 사용하는 방법이죠. 구체화를 통한 추상화

 

728x90

 

결국 아래와 같은 식이 성립한다는 것을 알아낼 수 있었습니다.

P(x) = P(x-1) + P(x-5)

그럼 이제 단순 DP 문제가 되었네요. Bottom up 방식으로 풀었습니다.

 

참고로 몇 가지 수학적인 과정을 거치면, 아래 식도 성립한다는 것을 알 수 있습니다.

P(x) = P(x-2) + P(x-3)

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=9oFumQsFjEE 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)