https://www.acmicpc.net/problem/15990
1 만드는 경우 : [1] --> 1개
2 만드는 경우 : [2] --> 1개
3 만드는 경우 : [1+2, 2+1, 3] --> 3개
4 만드는 경우 : [1+2+1, 1+3, 3+1] --> 3개
5 만드는 경우 : [1+3+1, 2+1+2, 2+3, 3+2] --> 4개
6 만드는 경우 : [1+2+1+2, 1+2+3, 1+3+2, 2+1+2+1, 2+1+3, 2+3+1, 3+1+2, 3+2+1] --> 8개
같은 수를 두번 이상 연속으로 붙이는 안되는 조건이 있었습니다.
이를 위해, 식의 가장 앞 숫자가 1 또는 2 또는 3으로 끝났을 때의 경우의 수를 각각 구분하여 구해줬습니다.
dp[i][j]는 숫자 i를 만들었을 때, 식의 가장 앞 숫자가 (j+1)인 경우의 수입니다.
예를 들어, 5를 만드는 경우의 수를 구해보겠습니다.
4를 만드는 경우의 앞 자리에 1을 덧붙여 5를 만들어보겠습니다.
가장 앞 숫자가 1로 끝날 때의 5를 만드는 경우의 수(dp[5][0])는, 4를 만드는 경우의 수에서 앞자리가 2 또는 3이어야만 합니다.
따라서, dp[5][0] = dp[4][1] + dp[4][2];
3을 만드는 경우의 앞 자리에 2을 덧붙여 5를 만들어보겠습니다.
가장 앞 숫자가 2로 끝날 때의 5를 만드는 경우의 수(dp[5][1])는, 3를 만드는 경우의 수에서 앞자리가 1 또는 3이어야만 합니다.
따라서, dp[5][1] = dp[3][0] + dp[3][2];
2를 만드는 경우의 앞 자리에 3을 덧붙여 5를 만들어보겠습니다.
가장 앞 숫자가 3으로 끝날 때의 5를 만드는 경우의 수(dp[5][2])는, 2를 만드는 경우의 수에서 앞자리가 0 또는 2이어야만 합니다.
따라서, dp[5][2] = dp[2][0] + dp[2][1];
n을 만드는 경우의 수는 dp[n][0] + dp[n][1] + dp[n][2] 입니다.
#include <cstdio>
#define MOD 1000000009
int main() {
int t, n;
long long int dp[100001][3] = { 0,0,0,1, 0, 0, 0,1,0, 1,1,1 };
scanf("%d", &t);
for (int i = 4; i <= 100000; i++) {
dp[i][0] = dp[i - 1][1] + dp[i - 1][2] % MOD;
dp[i][1] = dp[i - 2][0] + dp[i - 2][2] % MOD;
dp[i][2] = dp[i - 3][0] + dp[i - 3][1] % MOD;
}
while (t--) {
scanf("%d", &n);
printf("%lld\n", (dp[n][0] + dp[n][1] + dp[n][2]) % MOD);
}
}
'Algorithm' 카테고리의 다른 글
백준 2193 : 이친수 (0) | 2021.11.12 |
---|---|
백준 11057 : 오르막 수 (0) | 2021.11.12 |
백준 16194 : 카드 구매하기 2 (0) | 2021.11.12 |
백준 11052 : 카드 구매하기 (0) | 2021.11.12 |
백준 15988 : 1, 2, 3 더하기 3 (0) | 2021.11.12 |