[백준] JAVA 자바 : 1, 2, 3 더하기 3 (15988번)

---

앞서 1, 2, 3 더하기 문제들과 큰 차이가 없는 문제다.
그런데 솔직히 이제와서 그 문제가 뭐였는지 기억도 안 나서 ㅋㅋ 그냥 다시 짰다.

 

N은 1~1000000 사이의 수이므로 1000001까지의 long 배열을 만든 후 1, 2, 3을 더해서 만들 수 있는 모든 경우의 수를 다 저장한다.

그리고 for문을 돌면서 n을 입력받을 때마다 dp[n]을 출력하면 된다.

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

public class Sum123_3 {

    static int MOD = 1000000009;

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

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

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

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

        int T = stoi(br.readLine());
        for (int i=0; i<T; i++) {
            int n = stoi(br.readLine());
            System.out.println(dp[n]);
        }

    }
}

 

로그인

 

 

작성일자: 2024-01-17