👀 문제
https://www.acmicpc.net/problem/15988
👊 도전
1. 설계
- n이 1000까지로 범위가 정해져있고, 규칙이 있을 것 같으므로 DP를 이용한다.
- dp를 더해주는 과정에서 int형을 벗어날 수 있으므로 더할 때마다 주어진 값으로 나머지 연산을 해준다.
2. 구현 (성공 코드)
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
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t=scan.nextInt();
int[] dp=new int[1000001];
for(int i=1;i<1000001;i++) {
if(i==1) dp[1]=1;
else if(i==2) dp[2]=2;
else if(i==3) dp[3]=4;
else {
dp[i]+=dp[i-1];
dp[i]%=1000000009;
dp[i]+=dp[i-2];
dp[i]%=1000000009;
dp[i]+=dp[i-3];
dp[i]%=1000000009;
}
}
while(t>0) {
t--;
int n=scan.nextInt();
System.out.println(dp[n]);
}
}
}
3. 결과
🤟 성공 🤟
나머지 연산 때문에 많이 틀렸다. 다 더한 후 나머지 연산을 한 번해도 범위를 충분히 초과할 수 있다. 각 값을 더할 때 마다 나머지 연산을 하여 범위가 벗어나지 않도록 해줬다.
4. 설명
- DP 규칙을 찾아낸다
- dp[1]=1, dp[2]=2, d[3]=4, dp[4]=7, dp[5]=13이다.
- i=4부터 dp[i]=dp[i-1]+dp[i-2]+dp[i-3] 규칙이 생긴다.
- int형을 벗어나지 않게 나머지 연산을 적절히 사용한다
- dp배열을 long형으로 선언했다면 별 상관없지만, int형으로 선언하였으므로 int형을 넘어가지는 않는지 확인해줘야한다.
- 값을 더할 때마다 나머지 연산을 해줘서 범위가 벗어나지 않도록 조절한다.