[백준, 9461번] 파도반 수열 (동적 프로그래밍 : DP , Java)

문제설명

입력 & 출력

나의 풀이

문제 접근

이번 "백준 - 파도반 수열" 문제는 문제에서 알 수 있듯이 파도반 수열을 구현하는 문제입니다.

[TIL, 일일 회고] 2024.12.10 - 파도반 수열이란❓

 

점화식을 알고있다면 정말 간단히 풀 수 있는 문제이지만 모르더라도, 그림을 보고 유추할 수 있습니다.

1번째 부터 3번째 까지는 제외하고, 4번째 삼각형부터 본다면, 두 번째와 세 번째 이전 항의 합이 N번째 항인 것을 유추할 수 있습니다.

 

따라서 점화식은 다음과 같습니다.

P(n) = P(n−2) + P(n−3)

 

전체 코드

 

다이나믹 프로그래밍 알고리즘을 사용한다면 효율적으로 P(N)을 구할 수 있습니다.

[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기

 

N이 (1 ≤ N ≤ 100)의 범위로 주어지기 때문에 미리 dp 배열을 선언해주고, 각 수를 구해주고, N번째 항을 출력하여 마무리해줬습니다.