(2482) 색상환

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

단계별로 풀어보기

40단계(동적 계획법 3) 6번째

 

 

 

dp[x][y]를 x번째 색까지 탐색하여 y개의 색을 선택했을 때 경우의 수라고 하자.

x번째 색을 선택했다면 x-2번째 색까지 y-1개를 선택했고, 선택하지 않았다면 x-1번째 색까지 y개를 선택했으므로

dp[x][y]= dp[x-2][y-1]+dp[x-1][y]이다

1번과 N번 색은 동시에 선택할 수 없으므로 1번을 선택한 경우와 아닌 경우로 나눠야 한다.

1) 1번을 선택한 경우 dp[x][0]= 0(x>0일 때), dp[x][1]= 1이다. 몇 번까지 탐색을 하든 1번을 이미 선택했기 때문이다. 이 경우 N번은 선택할 수 없으므로 dp[N-1][k]가 구하는 경우의 수다.

2) 1번을 선택하지 않은 경우 dp[x][0]= 1, dp[x][1]= x-1이다. 선택하지 않는 경우가 하나 있고, x번까지 색 중 1번을 빼고 하나를 택하는 경우는 x-1이기 때문이다. 이 경우 N번도 선택할 수 있으므로 dp[N][k]가 구하는 경우의 수다.

두 경우를 각각 계산해 합치면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define p 1000000003

int main() 
{
  int n, k, ans= 0;
  
  cin >> n >> k;
  
  vector dp(n, vector<int> (k+1));
  
  // 1번째 색 선택
  for(int i=0;i<n;i++)  dp[i][1]= 1;
  
  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])%p;
    }
  }
  
  ans+= dp[n-2][k];
  
  dp= vector (n, vector<int> (k+1));
  
  // 1번째 색 미선택
  for(int i=0;i<n;i++){
    dp[i][0]= 1;
    dp[i][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])%p;
    }
  }
  
  ans+= dp[n-1][k];
  
  cout << ans%p;
  
  return 0;
}