다이나믹 프로그래밍_15990 : 1,2,3 더하기 5 JAVA
1, 2, 3 더하기 5 성공
| 1 초 (추가 시간 없음) | 512 MB | 29100 | 9786 | 6891 | 30.809% |
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
- 1+2+1
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
예제 입력 1 복사
3
4
7
10
예제 출력 1 복사
3
9
27
같은 수가 연속해서 오지 못한다는 조건이 생겼다. 단순히 수를 만들기 위한 경우의 수만 저장해서 풀 수 없다.
1. N을 만들기 위한 경우의 수
2. 그 수식의 마지막이 어떤 수로 끝나는 지
이 두가지를 알 수 있게 저장해야 한다.
4를 1,2,3의 합으로 나타내는 경우의 수를 알아본다.
4를 만드는 수식중 마지막이 1로 끝나는 것의 수
3을 만드는 수식중 마지막이 2로 끝나는 것의 수 + 1
3을 만드는 수식중 마지막이 3으로 끝나느 것의 수 + 1
arr[4][1] = arr[3][2] + arr[3][3]
4를 만드는 수식중 마지막이 2로 끝나는 것의 수
2를 만드는 수식중 마지막이 1로 끝나는 것의 수 +2
2를 만드는 수식중 마지막이 3으로 끝나는 것의 수+2
arr[4][2] = arr[2][1] + arr[2][3]
4를 만드는 수식중 마지막이 3으로 끝나는 것의 수
1을 만드는 수식중 마지막이 1로 끝나는 것의 수 +3
1을 만드는 수식중 마지막이 2로 끝나는 것의 수 +3
arr[4][3] = arr[1][1] + arr[1][2]
이 세경우를 점화식으로 만들면 이렇게 나온다.
arr[i][1] = arr[i-1][2] + arr[i-1][3]
arr[i][2] = arr[i-2][1] + arr[i-2][3]
arr[i][3] = arr[i-3][1] + arr[i-3][2]
import java.io.*;
public class Main{
static long[][] arr = new long[100001][4];
static int MOD = 1000000009;
public static void main(String[] args){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
arr[1][1] = 1;
arr[2][2] = 1;
arr[3][1] = 1;
arr[3][2] = 1;
arr[3][3] = 1;
for(int i=4;i<arr.length;i++){
arr[i][1] = (arr[i-1][2] + arr[i-1][3]) % MOD;
arr[i][2] = (arr[i-2][1] + arr[i-2][3]) % MOD;
arr[i][3] = (arr[i-3][1] + arr[i-3][2]) % MOD;
}
int t = Integer.parseInt(br.readLine());
while(t-->0){
int num = Integer.parseInt(br.readLine());
long result = (arr[num][1] + arr[num][2] + arr[num][3]);
sb.append(result).append('\n');
}
System.out.println(sb);
}
}