[JAVA] 백준 15988번- 1, 2, 3 더하기 3

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

 

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 T = Integer.parseInt(br.readLine());

        long[] dp = new long[1000001];

        dp[1] = 1; // 1
        dp[2] = 2; // 1+1, 2
        dp[3] = 4;// 1+1+1, 1+2, 2+1, 3

        for(int i=4; i<1000001; i++){
            dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % 1000000009;
        }

        while(T-->0){
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }
        System.out.println(sb);
    }
}

 

https://yeoncoding.tistory.com/594

[JAVA] 백준 9095번- 1, 2, 3 더하기

 

 

1,2,3 더하기 문제와 dp를 세우는 방법은 같다. 

달라진 점은 n의 범위가 1,000,000까지 라는 것, 결괏값에서 1,000,000,009를 나눈 나머지를 출력해야 한다는 것이다.

 

dp 점화식을 진행하며 덧셈을 하면 int 범위를 초과할 수 있다. 

예를 들어 dp[n-1], dp[n-2], dp[n-3] 이 각각 10억이라고 하면 다 더한 값은 int 범위인 20억을 넘어버린다. 

그러므로 dp 배열의 타입을 long 으로 해줘야 한다.

 

또 마지막 출력할 때만 % 1,000,000,009 를 해주면 계산 중간에 오버플로우가 발생하기 때문에dp를 계산 할때마다 % 연산이 적용된 dp[n]을 저장해줘야 한다.