백준 15988 1,2,3 더하기 3

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

문제해결

기존 1, 2, 3 더하기 문제를 풀어봤다면 크게 어렵진 않았을 것이다. 이 문제의 핵심은 n이 1,000,000보다 작거나 같아서 오버플로우가 나지 않도록 주의하는 것이다.
int 범위를 벗어나서 long 타입으로 선언해주었으며, 연산 중간과정에서 나머지 연산을 처리해주었다.

기존 소스코드로 풀이하였을 때 점화식도 맞고 답도 맞는데 계속 시간초과가 났다. 맞는데 어디가 틀린거지 한참을 헤매다가 다른 사람들이 질문한 글을 보고 불필요한 연산을 계속하면서 시간초과가 나는 것을 확인할 수 있었다. 내 코드를 맹신하지 않기로 했다.

소스코드

import java.io.*;

public class b15988 {
    static long[] dp = new long[1000001];
    static long mod = 1000000009L;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i < 1000001; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
        }
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            bw.write(dp[n] + "\n");
        }
        bw.flush();
        bw.close();
    }
}

기존 소스코드

import java.io.*;

public class b15988 {
    static long[] dp = new long[1000001];
    static long mod = 1000000009L;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 4;
            for (int i = 4; i < 1000001; i++) {
                dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
            }
            bw.write(dp[n] + "\n");
        }
        bw.flush();
        bw.close();
    }
}

이렇게 해도 답은 나옵니다. 단지 불필요한 연산과정에서 시간초과가 뜰 뿐 ㅎㅎ