색상환 (BOJ 2482)

문제

이미지클릭

문제 설명

• n개의 색들이 주어지는 데 인접한 색을 동시에 사용하지 않을 려고 한다.
• K개의 색을 뽑는 경우의 수를 구해야 한다.

최종 코드

#include<bits/stdc++.h>
#define MOD 1000000003 
using namespace std;

int n, k;
long long dp[1004][1004];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    
    if (n < k * 2) {
        cout << 0;
        return 0;
    }
    
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
        dp[i][1] = i;
        //0개를 뽑는 경우는 1가지
        //1개를 뽑는 경우는 i가지
    }
    
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= k; j++) {
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % MOD;
            //dp[i - 2][j - 1]: 현제 색을 선택하는 경우
            //dp[i-1][j]: 현제 색을 선택하지 않고 넘어가는 경우
        }
    }
    
    cout << (dp[n - 1][k] + dp[n - 3][k - 1]) % MOD;
    //dp[n - 1][k]: 첫번째 색을 선택하는 경우
    //dp[n-3][j-1]: 첫번째 색을 선택하지 않는 경우
}

문제 해설

dp[a][b]

a: 색의 개수
b: 색을 뽑는 개수

dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % MOD;

색을 뽑을 때 인접한 색을 뽑을 수 없기 때문에 두 가지의 경우로 나누어 봐야 한다.
1. 현제 색을 선택하는 경우: dp [i - 2][j - 1]
- i번 째 색을 선택하기 위해서는 i-1번째가 아니라 i-2번째 색까지의 경우를 선택해야 한다.

2. 현제 색을 선택하지 않는 경우: dp [i-1][j]
-i-1번째 색까지 탐색한 경우 중에서 j개를 뽑은 경우를 선택해줘야 한다.

cout << (dp[n - 1][k] + dp[n - 3][k - 1]) % MOD;

여기에서 나오는 경우는 원형이기 때문에 dp [n][k]를 출력해 주면 안 된다.
그렇기에 첫 번째 색을 선택하는 경우와 선택하지 않는 경우로 나누어 줘야 한다.

1. 첫 번째를 선택하지 않는 경우: dp [n - 1][k]
-이 경우는 첫 번째만 제외한 n-1개의 경우를 찾아주면 된다.

2. 첫 번째를 선택하는 경우: dp [n - 3][k - 1]
-첫 번째 색을 뽑고 양옆을 사용할 수 없다고 가정하면 n-3개 중에서 j-1개를 뽑는 경우를 찾아주면 된다.

이미지클릭