코딩 테스트(Coding Test)/백준
[백준] 15990번 : 1, 2, 3 더하기 5
다문다뭉
2024. 12. 17. 14:16
Problem 🔒
문제
https://www.acmicpc.net/problem/15990
정수 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
Approach ⭕
이 문제는 동적 프로그래밍(DP)을 활용하여 풀 수 있다.
- 점화식 유도 과정
- 조건에서 같은 수를 두 번 이상 연속해서 사용하면 안된다는 것이 포인트다.
- 수 i를 만들 때, 해당 수식이 1,2,3으로 끝나는 개수를 각각 저장해야한다.
- dp[i][1] : 수 i를 만들고 수식이 1로 끝나는 경우
- dp[i][2] : 수 i를 만들고 수식이 2로 끝나는 경우
- dp[i][3] : 수 i를 만들고 수식이 3으로 끝나는 경우
- 점화식
- 수 N을 만들 때 해당 수식이 1로 끝나는 경우의 수
- 일단, 연속해서 1을 사용할 수 없으므로, 직전에는 2또는 3이 사용되었어야 한다.
- 그럼 수 (N-1)에서 수식이 2, 3으로 끝나는 경우에 1을 더해주면 된다.
- 수 N을 만들 때 해당 수식이 2로 끝나는 경우의 수
- 마찬가지로 직전에는 1 또는 3이 사용되었어야 한다.
- 수 (N-2)에서 수식이 1, 3으로 끝나는 경우에 2를 더해주면 된다.
- 수 N을 만들 때 해당 수식이 3으로 끝나는 경우의 수
- 직전에는 1 또는 2가 사용되었어야 한다.
- 수 (N-3)에서 수식이 1, 2로 끝나는 경우에 3을 더해주면 된다.
- 수 N을 만들 때 해당 수식이 1로 끝나는 경우의 수
- long 타입 배열 사용
- 항상 1000000009로 나눈 나머지를 저장하여 int 배열로 저장해도 문제 없을 것 같다.
- 하지만, 중간에 값을 더하는 연산 과정에서 int 범위를 벗어나면 오버플로우가 발생할 수 있다.
$dp[N][1]=dp[N−1][2]+dp[N−1][3]$
$dp[N][2]=dp[N−2][1]+dp[N−2][3]$
$dp[N][3]=dp[N−3][1]+dp[N−3][2]$
위 점화식을 통해 N≥4이므로, N=1,2,3은 초기값으로 설정해줘야한다.
Learned 😯
- 아직 dp에 익숙하지 않아서, 점화식 유도하는게 어려워 답안을 보고 풀 수 있었다.
- 연산 과정에서 int 범위를 벗어나면 오버플로우가 발생한다는 것을 알게 되었다.
Solution 💡
public class Main {
static int T, N;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
long[][] map = new long[100001][3];
map[1][0]=1; map[2][1]=1; map[3][0]=1; map[3][1]=1;
map[3][2]=1; map[4][0]=2; map[4][2]=1;
for(int i=4; i<map.length; i++){
map[i][0] = (map[i-1][1] + map[i-1][2])%1000000009;
map[i][1] = (map[i-2][0] + map[i-2][2])%1000000009;
map[i][2] = (map[i-3][0] + map[i-3][1])%1000000009;
}
while(T-->0){
N = Integer.parseInt(br.readLine());
sb.append((map[N][0] + map[N][1] + map[N][2])%1000000009).append("\\n");
}//T
System.out.println(sb);
}
}