태그:
N번째 파도반 수를 구하는 문제입니다. 점화식을 구한 후 DP를 이용하여 풀 것인데, 이 문제는 그림에 힌트가 있습니다(그림은 문제 참조). 그림을 자세히 보면 n번째 삼각형의 변의 길이는 n-1번째 삼각형과 n-5번째 삼각형의 변의 길이의 합입니다. 즉, \(a_n=a_{n-1}+a_{n-5},a_1=a_2=a_3=1,a_4=a_5=2\)입니다. 이를 피보나치 수열을 구하는 방법과 유사한 방법으로 재귀 함수와 memoization을 통해 구현하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-31 14:24:48 |