2482 색상환
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MOD 1000000003
int DP[1003][1003];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i <= n; i++) {
DP[i][1] = i;
DP[i][0] = 1;
}
for (int i = 4; i <= n; i++)
for (int j = 2; j <= k; j++)
DP[i][j] = (DP[i - 2][j - 1] + DP[i - 1][j]) % MOD;
cout << DP[n][k] % MOD << '\n';
return 0;
}
DP[i][j]는 i개의 색상환에 포함된 색 중 j개의 색을 선택할 때 고를 수 있는 경우의 수다.
i개 색 중 1개를 택하는 경우의 수는 i개, i개 색 중 0개 색을 택하는 경우의 수가 1개인 것은 쉽게 알 수 있으므로 초기화해준다.
색상환을 선형으로 펼쳐서 생각한다면, 다음의 표와 같이 두 경우로 나누어 나타낼 수 있다.
첫번째 열은 i번째 색을 선택한 경우고, 두번째 열은 i번째 색을 선택하지 않은 경우이다.
1 | 2 | ... | i-2 | i-1 | i |
이 | 중 | j-1 개 | 선택 | (선택 못함) | O |
이 | 중 | j | 개 | 선택 | X |
i번째 색을 선택한 경우에는 i-1번째 색은 자동으로 선택하지 못하고, 나머지 1 ~ i-2번째 색 중에서 j-1개의 색을 택하는 경우와 같을 것이다.
i번째 색을 선택하지 않은 경우에는 1 ~ i-1번째 색 중에서 j개의 색을 택하는 경우와 같을 것이다.
따라서 점화식을 DP[i][j] = DP[i-2][j-1] + DP[i-1][j]와 같이 나타낼 수 있고, modulo 연산의 속성에 의해 한번 계산할 때마다 1,000,000,003으로 나눈 나머지를 넣어주면 전체 경우의 수를 1,000,000,003으로 나눈 경우의 수와 같게 된다.
'Algorithm > BOJ (백준)' 카테고리의 다른 글
[C/C++] 백준 14501 퇴사 (0) | 2020.07.27 |
---|---|
[C/C++] 백준 12865 평범한 배낭 (1) | 2020.07.26 |
[C++] 백준 11054 가장 긴 바이토닉 부분 수열 (0) | 2020.07.25 |
[C++] 백준 1937 욕심쟁이 판다 (0) | 2020.07.25 |
[C++] 백준 11066 파일 합치기 (0) | 2020.07.25 |