BOJ 2482: 색상환 작성일 2020-03-03 https://www.acmicpc.net/problem/2482 3월동안 210문제 풀기 (9/210) 어거지 DP로 어떻게든 풀었음 이건 규칙을 제대로 찾아서 더 효율적으로 풀어봐야함. 123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 1e9+3; int N, K; LL dp[2][2][1001][502]; LL go(int first, int prev, int cur, int remain) { if(N-cur < (remain-!first)*2) return 0; if(remain == 0) return 1; if(cur == N-1) { if(remain == 1 && first == 0 && prev == 0) return 1; else return 0; } if(dp[first][prev][cur][remain] != -1) return dp[first][prev][cur][remain]; LL ans = 0; if(!prev) ans = (ans + go(first, 1, cur+1, remain-1)) % MOD; ans = (ans + go(first, 0, cur+1, remain)) % MOD; return dp[first][prev][cur][remain] = ans; } int main() { cin >> N >> K; memset(dp, -1, sizeof(dp)); LL ans = 0; ans = (ans + go(1, 1, 1, K-1)) % MOD; ans = (ans + go(0, 0, 1, K)) % MOD; cout << ans; }