백준 2482번 : 색상환

  이 문제가 약간 까다로운 이유는 고리 형태이기 때문에 처음과 끝이 이어져있기 때문이다. 그래서 인접했는지를 판단할 때 처음과 끝을 특수하게 새로 판단해줘야 하는데 나는 이 부분을 처음에는 고려하지 않고 나중에 출력할 때만 고려함으로써 깔끔하게 풀었다.

---

  역시 dp문제이므로 dp를 잘 정의해보자.

 

dp[n][k] : n개의 색이 일렬로 있을 때, k개의 색을 인접하지 않게 고르는 경우의 수

 

  여기서 포인트는 문제의 상황과는 다르게 일렬로 있을 때로 dp를 설정하는 것이다. 이 dp를 구하는 방법은 어렵지 않다. n-1개의 색이 있는 상태에서 제일 끝에 하나의 색을 추가한다고 가정해보자. 그럼 상황은 두 가지로 나뉜다.

 

1. n번째 색을 선택하는 경우

2. n번째 색을 선택하지 않는 경우

 

  1. n번째 색을 선택하는 경우 인접하지 못한다는 조건에 의해 n-1번째 색은 절대로 선택할 수 없다. 따라서 n-2개의 색에서 k-1개를 고르면 되므로 dp[n-2][k-1]이다. 2. n번째 색을 선택하지 않는 경우 n번째 색이 없는 것과 마찬가지 이므로 n-1개의 색에서 k개를 고르면 되므로 dp[n-1][k]이다.

 

dp[n][k] = dp[n-2][k-1] + dp[n-1][k]

 

  그러면 마지막에 이 일렬로 배열되어 있는 상황을 어떻게 고리로 변형시키느냐는 문제만 남았다. 의외로 간단하다. n개의 색 고리가 있을 때 1. 첫 번째 색(12시 방향에 있는 색)을 고른다고 가정해보자. 그러면 그 색을 포함해 왼쪽 색과 오른쪽 색은 자동적으로 고를 수 없다. 그러므로 일렬로 있을 때 n-3개의 색에서 k-1개의 색을 고르는 것과 동일해진다. 2. 첫번째 색을 고르지 않는다고 가정해보면 일렬로 있을 때 n-1개의 색에서 k개의 색을 고르는 것과 동일해진다.

 

circle_dp[n][k] = dp[n-3][k-1] + dp[n-1][k]

 

#include <iostream>

using namespace std;

int n, k;
int dp[1002][1002];
int DIV = 1000000003;

int main()
{
    cin >> n >> k;
    
    for(int i = 0; i <=n ; i++) dp[i][0] = 1;
    
    dp[1][1] = 1;
    
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; 2 * j <= i + 1; j++)
        {
            dp[i][j] = (dp[i-2][j-1] + dp[i-1][j]) % DIV;
        }
    }
    
    cout << (dp[n-3][k-1] + dp[n-1][k]) % DIV;

    return 0;
}