색상환#

색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.

색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.

주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다.

주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.

일단 문제를 보고서 생각할 것 없이 나는 이 문제가 dp 문제인 것을 알고 들어왔다. 그래서 바로 dp 정의를 생각해 보았는데… 생각보다 어려웠다. 아직 내가 dp에 대해서 잘 모르는 것을 뼈저리게 느낀 문제였다.

일단 내 풀이 방법은 간단하다. dp[i][j][k]는 0~i 번째 까지의 색을 고려할 때, j개의 색을 고른다.

1. k = 0
   • 0~i번째 까지의 색을 고려할 때, j개의 색을 고르는데 현재의 단계 즉 i번째를 제외한 j개를 고른다.
2. k = 1
   • 0~i번째 까지의 색을 고려할 때, j개의 색을 고르는데 현재의 단계 즉 i번째를 포함한 j개를 고른다.

이렇게 정의를 하고 점화식을 짜러 들어갔다.

일단 현재 나 자신이 선택될 수 있는 조건이 무엇인가? 를 생각했다. 내가 선택이 가능하다는 것, 그리고 내가 설계한 dp 구조에서는 현재의 나를 마지막 보니까 “내 위치 - 1”의 색을 고르지만 않으면 된다.

그래서 현재 나를 고를 때 나는 무엇을 고려하냐 바로 dp[i-1][j-1][0]만을 고려하여 더하면 된다.

나를 선택하지 않는다는 것은 나의 전 상태를 고려할 수 있다는 의미이다. 그래서 dp[i-1][j][1]을 더한다. 그런데 내가 활성화되지 않았어도, dp[i-1][j][0]을 고려할 수 있다 그래서 결과적으로 dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1] 이렇게 된다.

정리해보자

k = 0일때
dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1]

k = 1일때
dp[i][j][1] = dp[i-1][j-1][0]

이런 점화식을 만들 수 있다.

당연하겠지만 초기에 설정되는 값이 굉장히 중요하다. 왜냐하면 문제가 원형 문제기 때문에 N 위치에 있는 색을 고르지 않앗을 때와 N의 위치를 고를 때의 처음 값을 다르게 설정하여 문제를 풀었다.

#include <iostream>
#include <algorithm>
#define MOD 1000000003
using namespace std;
int N, K;
int dp[1001][1001][2];

int solution(int n, int k, bool check){
    
    if(k*2 -1 > n) return 0;
    
    if(dp[n][k][check] != -1) return dp[n][k][check];
    
    if(check) dp[n][k][check] = solution(n-1, k-1, false) % MOD;
    else dp[n][k][check] = (solution(n-1, k, true) + solution(n-1, k, false)) % MOD;
    return dp[n][k][check];
}

int main(){
    cin >> N >> K;
    int result = 0;
    
    if(K == 1){
        cout << N;
        return 0;
    }
    for(int i = 0; i < N+1; i++){
        for(int j = 0; j < K+1; j++){
            dp[i][j][false] = -1;
            dp[i][j][true] = -1;
        }
        
        dp[i][0][false] = 1;
        dp[i][0][true] = 0;
        
        dp[i][1][true] = 1;
        dp[i][1][false] = i-1;
    }
    result += solution(N, K, false) % MOD;
    
    for(int i = 0; i < N+1; i++){
        for(int j = 0; j < K+1; j++){
            dp[i][j][false] = -1;
            dp[i][j][true] = -1;
  
        }
        dp[i][1][true] = 1;
        dp[i][1][false] = i-2;
  
    }
    for(int j = 0; j < K+1; j++){
        dp[1][j][false] = 0;
        dp[1][j][true] = 0;
        dp[0][j][false] = 0;
        dp[0][j][true] = 0;

    }

    result += solution(N, K, true);
 
    cout << (result % MOD) << "\n";


    return 0;
}