[백준 9461, Java] 파도반 수열

문제

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

풀이

 - 그림을 볼 필요 없이 수열을 보면 점화식을 구할 수 있다. f(n) = f(n-2) + f(n-3) (단 n=1,2,3일 때는 1)

- 구한 점화식을 가지고서 topDown방식, bottomUp 방식으로 풀 수 있다.

- 이때 주의해야할 점은 문제에서 주어지는 n은 "n번째"의 개념이기 때문에 메모이제이션의 배열 index와 구분해야한다. 

- 그리고 답의 범위는 long

 

코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int T;
    public static int N;
    public static long[] numArray;
    public static long[] memo;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine());
        N=101;
        numArray = new long[N];
        memo = new long[N];

        for(int t = 0; t<T; t++){
            int n = Integer.parseInt(br.readLine());
            long result = bottomUp(n);
            bw.write(String.valueOf(result)+"\n");
        }

        bw.flush();

    }

    public static long topDown(int n){
        if(n<3){
            memo[n] =1;
            return 1;
        }
        else if(memo[n]!=0){
            return memo[n];
        }
        else{
            memo[n] = topDown(n-2) + topDown(n-3);
            return memo[n];
        }
    }

    public static long bottomUp(int n){
        if(memo[n] !=0){
            return memo[n];
        }

        for(int index = 1; index<=n; index++){
            if(index<=3){
                memo[index] = 1;
            }
            else{
                memo[index] = memo[index-2] + memo[index-3];
            }
        }
        return memo[n];
    }
}