[백준 9461] 파도반 수열

^^

 

틀린 이유는 자료형 때문이었다.

dp 배열을 Long으로 변경하니까 해결되었다.

 

int 범위는 약 -2,147,483,648 ~ 2,147,483,647 이다.

dp[i] = dp[i - 2] + dp[i - 3] 계산 과정에서 100번째 값까지 계산하면

피보나치와 비슷한 증가 속도 때문에 int 범위를 초과한다.

 

dp[100] = 18,446,744,073,709,551,615 (약 18경)

 

코드

import java.io.*;

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

        // dp
        Long[] dp = new Long[101];
        dp[1] = 1L;
        dp[2] = 1L;
        dp[3] = 1L;

        for(int i=4; i<dp.length; i++){
            dp[i] = dp[i-2] + dp[i-3];
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<T; i++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }

        System.out.print(sb);
    }
}