[Algorithm]Baekjoon 2482번 : 색상환

https://www.acmicpc.net/problem/2482

2482번: 색상환

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int MOD = 1000000003;
 
int n, k;
int dp[1001][1001] = { 0 };
 
int SelectColor(int colorCount, int selectCount)
{
    if (colorCount >= 1 && selectCount == 1) return colorCount;
    if (colorCount < selectCount * 2) return 0; // 반드시 colorCount는 selectCount보다 2배이상이여야함.
    if (dp[colorCount][selectCount] != -1) return dp[colorCount][selectCount];
    
    int a = SelectColor(colorCount - 2, selectCount - 1) % MOD;
    int b = SelectColor(colorCount - 1, selectCount) % MOD;
 
    return dp[colorCount][selectCount] = (a + b) % MOD;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    memset(dp, -1, sizeof(dp));
 
    cout << SelectColor(n, k);
}

 

이것도 뭔가.. 나름 스탠다드한 유형의 문제라고 생각한다.

n개의 원형형태의 색깔 그래프가 주어졌을 때, k개의 색을 선택하는 경우의 수를 구해야하는데 인접된 색을 선택해선 안된다.

즉, 1번컬러를 선택했으면 2번은 건너뛰고 3번을 선택해야한다.

dp문제를 좀 풀어봤다면, 점화식자체는 금방 생각할 수 있을수도 있다. 다만 예외처리에서 살짝 애먹을 수 있긴하다.

 

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

 

이게 점화식인데, 앞의 식인 dp[n-2][k-1]은 현재 색을 선택했다는 의미이다. 그렇기 때문에 그 다음색인 n-1을 선택하면 안되고, 한칸 건너뛰어서 n-2를 선택해야하며 현재 색을 선택했기 때문에 선택횟수인 k를 1 차감시키는 것이다.

 

뒤의 식은 현재 색을 선택안했다는 의미이다. 그렇기 때문에 그 다음색인 n-1을 '선택가능'하다. (현재색을 선택안했으니까)

그렇기 때문에 n-1이며, 마찬가지이유로 현재색을 선택안했기 때문에 선택횟수 k는 그대로 유지시켜 주면 된다.

 

탐색을 진행하다 선택횟수가 1이라면 (위 코드의 dfs함수의 두번째 매개변수), 현재 남은색깔을 그대로 리턴한다.

현재 남은 색깔이 총 3가지인데, 선택횟수가 1이라면 3개 각각을 선택한게 경우의 수가 되기 때문이다.

첫번째색을 선택해도 되고, 두번째색을 선택해도 되고, 세번째색을 선택해도 된다.

그렇기 때문에 dp[3][1] == 3이 된다.

 

그리고 선택할수있는 컬러의 개수는 항상 선택횟수보다 2배이상을 유지해야 한다.

즉, colorCount >= selectCount *2      를 유지해야 한다는 것이다. 이것을 유지하지 못할경우 바로 return 0 하면된다.

왜?  유지하지 못하면 인접한 색깔을 고를수밖에 없는 경우밖에 존재하지 않기 때문이다.