[C++] 백준 9461번 파도반 수열

다이나믹 프로그래밍 문제.

친절하게 P(1)부터 P(10)까지의 값이 모두 주어졌다.

DP는 Bottom Up 방식으로 풀면 주어지는 값이 많으면 많을수록 유추하기 쉽기 때문에 풀기 쉽다.

 

문제풀이

주어지는 값들의 규칙을 찾아보면

점화식을 바로 찾을 수 있다.

n>=4일때,

An = A(n - 2) + A(n - 3) 이다.

 

코드 전문

코드가 짧다. n이 4부터 시작하므로 1, 2, 3값은 초기화를 미리 시켜준다.

그리고 자료형은 long long으로 해주어야 오버플로우가 나지 않는다.

 

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.