문제
정수 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, 2, 3 의 더하기로 숫자를 나타낼 수 있는데 연속된 숫자는 사용할 수 없다는 것이다.
따라서 마지막 숫자가 1, 2, 3 인 경우에 뒤에 올 수 있는 숫자의 경우가 나눠지므로
dp[n][4] 로
dp[n][1] 은 n 의 숫자를 표현할 때 마지막으로 1을 더하는 경우
dp[n][2] 은 n 의 숫자를 표현할 때 마지막으로 2를 더하는 경우
dp[n][3] 은 n 의 숫자를 표현할 때 마지막으로 3을 더하는 경우
와 같이 생각해볼 수 있다.
그러면 n 을 표현하기 위해서 1이 마지막으로 올 경우는 n - 1 숫자에서 끝이 2나 3으로 끝나는 경우로 생각해볼 수 있다.
n 에 마지막으로 1을 더해서 끝내기 위해서는 n - 1 의 숫자에서 1을 더해야 하는데
1이 연속되면 안되므로 2나 3으로 끝나는 경우에 대해서만 고려해야 한다.
2 와 3도 마찬가지이므로 점화식은 다음과 같이 된다.
- 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]
코드
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
for (int i = 0; i < T; i++)
{
long long arr[100001][4] = {
0,
};
long long n;
cin >> n;
arr[1][1] = 1;
arr[2][2] = 1;
arr[3][1] = 1;
arr[3][2] = 1;
arr[3][3] = 1;
for (int j = 4; j <= n; j++)
{
arr[j][1] = (arr[j - 1][2] + arr[j - 1][3]) % 1000000009;
arr[j][2] = (arr[j - 2][1] + arr[j - 2][3]) % 1000000009;
arr[j][3] = (arr[j - 3][1] + arr[j - 3][2]) % 1000000009;
}
cout << (arr[n][1] + arr[n][2] + arr[n][3]) % 1000000009 << "\n";
}
return 0;
}
리뷰
항상 백준 문제나 코테 문제를 풀 때 어렵고 시간이 많이 들인 문제가 DP 였다.
(아직 BST, DFS, BFS 같은 문제는 거의 풀지도 않았지만...)
그래도 점화식을 세워서 풀어보자! 해서 n 을 계속 전개가면서 풀어봤지만
도저히 점화식을 유도할 수 없었다....
결국 다른 사람의 풀이와 해설로 이해!하고 풀게 되었지만
단순히 n 의 값에 따른 규칙을 찾는다기 보다는 문제의 조건과 의도를 생각해서
점화식을 유도하는 것이 중요할 듯 하다!!!
