https://suhyeokeee.tistory.com/21
[백준 9095] 1,2,3 더하기 -JAVA //le_effort
전형적인 DP문제이다 일단 점화식은 dp [i] = dp[i-1]+dp[i-2]+dp[i-3] 인데 이걸 어떻게 도출하는지에 대해서 설명하겠다 모든 수를 1 , 2, 3 을 이용해서 만들어야 한다. dp[i] 는 i번째 수를 만들 수 있는 개..
suhyeokeee.tistory.com
이 문제에서 나누기만 해주면 된다.
주의 할 점:
|
1
2
3
4
5
6
|
for(int i=4; i<=1000000;i++) {
dp[i] += dp[i-3]%1000000009;
dp[i] += dp[i-2]%1000000009;
dp[i] += dp[i-1]%1000000009;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
이렇게 하면 틀린 답을 받게 된다.
dp[i]가 10억8이고 dp[i-3]이 10억 8 인 경우
dp[i] = 10억8 + 10억8이 된다.
그래서 다 더해주고 나눠줘야한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
public class Main {
static int n,t;
static StringBuilder sb = new StringBuilder();
static int dp[] = new int[1000001];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
t = Integer.parseInt(br.readLine());
dp[1]=1;
dp[2]=2;
dp[3]=4;
for(int i=4; i<=1000000;i++) {
dp[i] += dp[i-3];
dp[i]%=1000000009;
dp[i] += dp[i-2];
dp[i]%=1000000009;
dp[i] += dp[i-1];
dp[i]%=1000000009;
}
while(t-- >0) {
n = Integer.parseInt(br.readLine());
}
System.out.println(sb);
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
olor:white">cs |
