백준 9461번 : 파도반 수열 (JAVA)

🔗 문제 링크

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

---

📌 문제 개요

파도반 수열은 특정 규칙을 따르는 수열이다.
주어진 N에 대해 N번째 값을 구해야 한다.

 

여러 개의 테스트 케이스가 주어지며, 각각 결과를 출력한다.

---

📌 접근 방법

• DP 배열을 이용해 수열을 미리 계산
• 최대 N이 100이므로 한 번만 계산하면 충분
• 이후 입력받은 값에 대해 바로 출력

---

📌 핵심 아이디어

• 점화식 : P[n] = P[n-2] + P[n-3]
• 초기값 : P[1] = 1, P[2] = 1, P[3] = 1
• 값이 커지므로 long 사용

---

📌 전체 코드

package no_9461;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class No9461 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        long[] P = new long[101];
        P[1] = 1;
        P[2] = 1;
        P[3] = 1;

        for(int i = 4; i <= 100; i++){
            P[i] = P[i - 2] + P[i - 3];
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < T; i++){
            int N = Integer.parseInt(br.readLine());
            sb.append(P[N]).append("\n");
        }

        System.out.println(sb);
    }
}

 

---

📝 정리

• 피보나치와 비슷하지만 다른 점화식 사용
• DP로 미리 계산하는 것이 핵심
• 배열 크기 설정 실수 주의 (100 → ❌ / 101 → ⭕)