[BOJ 2482] 색상환

난이도가 있는 dp문제다.

언제나 그렇듯이 dp는 테이블로 시작해서 테이블로 끝난다.

dp는 테이블만 잘 설계한다면 물리적으로 내부동작이 어떻게 되든지 상관없이 논리적으로 답이 도출된다.

테이블이 설계가 안된다면 수열을 노가다로 찾아야 하는데 실수할 여지도 많고 시간이 얼마나 걸릴지도 알수 없다.

테이블을 잘 설계하면 이전값들의 결과가 현재값에 영향을 끼쳐야하는 형태가 돼야한다.(끊어지지 않고 이어지는 형태)

 

서론은 여기까지 하고 이제 이문제를 풀어보자.

일단 d[i][j]는 i개 중에서 j개를 선택하는 경우의 수라고 테이블을 설계했을때

딱 두가지 경우만 생각하면 이문제는 풀린다.

 

1. 첫번째 색을 포함할 것인가? -> 첫번째를 제외한(이미 뽑았음으로) 나머지 n-1개 중에서 k-1개를 마저 뽑는다.

2. 첫번째 색을 포함하지 않을 것인가? -> 첫번째를 제외한 나머지 n-1개 중에서 k개를 뽑는다.

 

그래서 점화식을 세우면 d[i][j] = d[i-2][k-1] + d[i-1][k] 이다.

빨간색을 주목하자. 여기서 왜 앞서 말한것과 같이 d[i-1][k-1]이 아니라 d[i-2][k-1]일까?

이 문제는 인접한 색을 뽑으면 안된다는 조건이 있었다. 즉 첫번째 색을 포함하게 된다면 색상환은 원형이기 때문에

맨 마지막색(n번째)은 포함될수 없어서 1을 더 빼줘야 하는것이다.

이렇게 점화식만 논리적으로 빈틈없이 잘세워 준다면 비교적 간결히 문제를 풀수있는것이 dp의 매력이 아닐까 싶다.

 

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

int d[1005][1005]; // d[i][j] i개 중에서 j개를 선택하는 경우의 수

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n,k;
  cin >> n >> k;

  for(int i=1; i<=n; i++) d[i][1] = i;

  for(int i=2; i<=n; i++){
    for(int j=2; j<=k; j++){
      if(j > i/2) break;
      d[i][j] = (d[i-1][j] + d[i-2][j-1]) % 1000000003;
    }
  }

  cout << d[n][k] << '\n';


}