[자바] 9461. 파도반 수열

package org.example.알고리즘.파도반수열;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int T = Integer.parseInt(br.readLine());
            int[] ns = new int[T];
            StringBuilder sb = new StringBuilder();
            
            for (int i = 0; i < T; i++) {
                ns[i] = Integer.parseInt(br.readLine());
            }
            
            int maxValue = Arrays.stream(ns).max().getAsInt();
            
            long[] dp = new long[102];
            
            dp[1] = 1L;
            dp[2] = 1L;
            dp[3] = 1L;
            dp[4] = 2L;
            dp[5] = 2L;
            dp[6] = 3L;
            dp[7] = 4L;
            dp[8] = 5L;
            dp[9] = 7L;
            dp[10] = 9L;
            
            for (int i = 11; i < maxValue + 1; i++) {
                dp[i] = dp[i - 1] + dp[i - 5];
            }
            
            for (int i = 0; i < T; i++) {
                sb.append(dp[Math.toIntExact(ns[i])]).append("\n");
            }
            
            System.out.println(sb);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

• 기본적인 DP 문제
  • 그림으로 유추해보면
  • dp [n] 의 경우 이전 n-1 + n-5 의 길이 더한 값과 동일
• 하지만,
  • 더한 값의 경우 N이 100에 근접할 수도록, int 범위 이상으로 number overflow 가 발생함
  • long 타입의 길이 배열로 선언해줘야한다.