백준 9461 파도반 수열 [JAVA]

Ga0·2023년 10월 29일

Java baekjoon 백준 자바

baekjoon

목록 보기

104/125

문제 해석

이 문제는 전 POST 였던 01타일문제와 매우 유사한 문제이다.
식이 조금 다른데, 그 외에는 거의 동일하다고 볼 수 있다. 이에 대한 설명은 아래와 같다.
일단 테스트의 개수 T를 입력받고 T만큼 P(N : T개마다 주어지는 숫자)을 구하면 되는 문제인데, 피보나치수와 좀 다르게 흘러가는 점은 값을 구하는 인덱스가 전이 아닌 전전 인덱스라는 것이다.
그림으로 설명하면 아래와 같다.
위와 같이 P(N) = P(N-2) + P(N-3) 값인 것을 확인할 수 있다.

코드

틀린 vers


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

public class Main {

    static int[] fib = new int[101];

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

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

        /*초기 값 설정*/
        fib[0] = 0;
        fib[1] = 1;
        fib[2] = 1;
        fib[3] = 1;

        for(int i = 4; i < fib.length; i++) {
            fib[i] = -1;
        }

        while(T --> 0){
            int N = Integer.parseInt(br.readLine());

            sb.append(P(N)).append("\n");
        }

        System.out.println(sb);
        br.close();
    }


    static int P(int N){

        if(fib[N] == -1){
            fib[N] = P(N-2) + P(N-3);
        }

        return fib[N];
    }
}

범위 값을 고려 안해서 틀린 버전이다. (N이 100이면 9000억 가까이 되기 때문에 int형 범위를 넘어가게 되고 이로 인해 정답처리가 되지 않았다...)

수정한 vers(정답)

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

public class Main {

    static Long[] fib = new Long[101];

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

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

        /*초기 값 설정*/
        fib[0] = 0L;
        fib[1] = 1L;
        fib[2] = 1L;
        fib[3] = 1L;

        while(T --> 0){
            int N = Integer.parseInt(br.readLine());

            sb.append(P(N)).append("\n");
        }

        System.out.println(sb);
        br.close();
    }


    static Long P(int N){

        /*Long은 Wrapper Class으로 값의 초기값이 null이기 때문에 초기화를 -1로 잡아줄 필요가 없다.*/
        if(fib[N] == null){
            fib[N] = P(N-2) + P(N-3);
        }

        return fib[N];
    }
}