[백준] 9461번 파도반 수열 _ JAVA ( 주석 설명 )

1번

→ 노트에 적으며 규칙을 찾아보면 다음과 같은 점화식을 얻을 수 있다.

f(n) = f(n-5) + f(n-1)

→ Top-down 방식

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

public class Main {
    //출력값 범위가 int max 값을 넘어가므로 long 배열로 만든다.
    static long[] dp = new long[101]; //중복 계산을 막기 위해 중간 결과값들을 저장하기 위한 배열이다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //규칙 정립을 위한 초기값 저장
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;
        dp[5] = 2;


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

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<T;++i){ //테스트케이스 숫자만큼 입력을 받는다.
            int N = Integer.parseInt(br.readLine());

            sb.append(solve(N)).append('\n');
        }

        System.out.println(sb); //입력받은 N번 정삼각형의 한 변의 길이를 출력한다.
    }

    //Top-down 방식
    private static long solve(int N){
        if(dp[N]>=1) //배열 안에 값이 들어가 있으면 그 값을 바로 return 한다.
            return dp[N];

        dp[N] = solve(N-5) + solve(N-1); //점화식을 찾고, 재귀로 N번째 정삼각형의 한 변의 길이를 구한다.

        return dp[N];
    }
}

 

---

 

2번

→ Bottom-up 방식

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

public class Main {
    //출력값 범위가 int max 값을 넘어가므로 long 배열로 만든다.
    static long[] dp = new long[101]; //중복 계산을 막기 위해 중간 결과값들을 저장하기 위한 배열이다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //규칙 정립을 위한 초기값 저장
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        dp[4] = 2;
        dp[5] = 2;


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

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<T;++i){ //테스트케이스 숫자만큼 입력을 받는다.
            int N = Integer.parseInt(br.readLine());

            sb.append(solve2(N)).append('\n');
        }

        System.out.println(sb); //입력받은 N번 정삼각형의 한 변의 길이를 출력한다.
    }

    //Bottom-up 방식
    private static long solve2(int N) {
        if(dp[N]>=1) //배열 안에 값이 들어가 있으면 그 값을 바로 return 한다.
            return dp[N];

        for(int i=6;i<=100;++i){ //6~100까지의 모든 값을 구한다.
            dp[i] = dp[i-5] + dp[i-1];
        }

        return dp[N];
    }
}