백준[2482] 색상환

문제 설명

풀이

이 문제는 dp를 이용하여 해결할 수 있다.

dp[N][K] = dp[N-2][K-1] + dp[N-1][K] (N: 현재 보고 있는 색, K: 현재까지 선택한 수)로 구할 수 있다.

나는 풀고 나서 왜 맞았는지 잘 모르겠어서 구글링하다가 여기를 발견했는데 정리를 너무 잘 해놓으셨다.

코드

#include <bits/stdc++.h>

using namespace std;

int dp[1003][1003];
int n, k;
const int mod = 1e9 + 3;

int dpf(int cur, int cnt) {
    int &ret = dp[cur][cnt];
    //cnt가 1이면 남은 것중에 아무거나 하나만 칠하면 됨
    if (cnt == 1) return cur;
    //cur이 2 * cnt보다 작으면 인접하는 경우가 무조건 한개 이상 나옴
    if (cur <= 0 || cur < 2 * cnt) return 0;
    if (~ret) return ret;
    return ret = (dpf(cur - 2, cnt - 1) + dpf(cur - 1, cnt)) % mod;
}

int main() {
    scanf("%d %d", &n, &k);
    memset(dp, -1, sizeof(dp));    
    printf("%d", dpf(n, k));
}

문제 링크 : https://www.acmicpc.net/problem/2482