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();
}
}
이렇게 해도 답은 나옵니다. 단지 불필요한 연산과정에서 시간초과가 뜰 뿐 ㅎㅎ