BOJ1029: 그림 교환 작성일 2020-06-01 https://www.acmicpc.net/problem/1029 흔한 bitmask dp이다. bottom-up으로 짜면, sliding windows를 할 수 있다. N=15를 보면 당연히 bitmask를 떠올려야 한다. 123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h> using namespace std; int N; vector<string> arr; int dp[15][10][1<<15]; int go(int owner, int price, int visit) { if(dp[owner][price][visit] != -1) return dp[owner][price][visit]; int ans = 1; for(int next = 1; next < N; next++) { if(visit & (1 << next)) continue; if(arr[owner][next] < price) continue; ans = max(ans, 1 + go(next, arr[owner][next], visit | (1 << next))); } return dp[owner][price][visit] = ans; } int main() { cin >> N; arr.resize(N); memset(dp, -1, sizeof(dp)); for(int i = 0; i < N; i++) cin >> arr[i]; for(string& s : arr) for(char& c: s) c -= '0'; cout << go(0, 0, 1); }