[Java] 백준(실버-3) 9461번 - 파도반 수열

문제 분석

---

작성코드

---

import java.io.*;
import java.util.*;

class Main {
    static long[] D;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // long형의 DP 테이블 초기화, N의 범위는 최대 100
        // 파도반 수열의 경우 N이 100일 때 int형의 범위를 넘어간다.
        // 그래서 반드시 long형 타입의 DP 테이블을 선언해야 한다.
        D = new long[101];
        // 1부터 5까지는 점화식에 해당되지 않기에 수동으로 초기화
        D[1] = 1;
        D[2] = 1;
        D[3] = 1;
        D[4] = 2;
        D[5] = 2;

        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            int N = Integer.parseInt(br.readLine());
            // N이 5 이하라면 이미 초기화된 값 반환
            if(N <= 5) {
                bw.write(D[N]+"\n");
            } 
            // N이 6 이상일 경우 재귀함수를 통해 P(N) 값 도출
            else {
                pado(N);
                bw.write(D[N]+"\n");
            }
        }

        bw.close();
        br.close();
    }
    static long pado(int n) {
        // 메모이제이션
        if(D[n] != 0) {
            return D[n];
        }
        // N이 6 이상일 경우 D[n] = D[n-1] + D[n-5]이라는 점화식 도출
        return D[n] = pado(n-1) + pado(n-5);
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.