Java 9461 파도반 수열

 

 

풀이 : 
dp문제는 sub문제들이 main 문제를 해결해주기 때문에 해당 규칙을 찾아내기 위해 수열을 나열해주었고 나열한 수열에서 i번째에 오는 수는 i-2 + i-3 이란 식을 도출해내었고 이를 memoization해주어 값들을 구한 뒤 입력받은 N을 출력해주었다. 

int형으로 값을 받으면 사이즈가 초과되니 long형으로 받아주었다.



처음엔 dp문제 푸는 게 너무 막막했는데 꾸준히 계속 풀다보니 요령이 조금 생기는 거 같아서 뿌듯했다.

top-bottom, bottom-top 두가지 방식으로 풀어보았다.

 

 

 

bottom-top

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

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

        long[] dp = new long[101];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for (int i = 3; i <= 100; i++) {
            dp[i] = dp[i-2] + dp[i-3];
        }
        for(int i = 0; i < n; i++){
            int j = Integer.parseInt(br.readLine());
            sb.append(dp[j]).append("\n");
        }
        System.out.println(sb);
    }
}

 

 

top-bottom

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

public class Main {

    static long[] dp;

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

        dp = new long[101];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;


        for (int i = 0; i < n; i++) {
            int j = Integer.parseInt(br.readLine());
            sb.append(recur(j)).append("\n");
        }
        System.out.println(sb);
    }
    public static long recur(int index){
        if(index <= 2){
            return dp[index];
        }
        if (dp[index] == 0) {
            dp[index] = recur(index - 2) + recur(index - 3);
        }
        return dp[index];
    }
}