백준 1029번: 그림 교환
9369 단어 bitmaskingpsDPcppDP
그림 교환
아이디어
현재 그림을 가지고 있는 예술가를 X, 그 예술가가 그림을 구매한 가격을 Y, 지금까지 그림을 소유해봤던 예술가의 목록을 Z라 하고 cache[X][Y][Z]에 메모이제이션 ㄱㄱ
코드
#include <bits/stdc++.h>
using namespace std;
int N;
int arr[15][15];
int cache[15][10][1<<15];
int solve(int artist, int price, int visited) {
if (visited == (1<<N)-1) {
return 0;
}
int& ret = cache[artist][price][visited];
if (ret != -1) return ret;
ret = 0;
for (int i = 0; i < N; i++) {
if (price > arr[artist][i]) continue;
if (visited&(1<<i)) continue;
ret = max(ret, solve(i, arr[artist][i], visited|(1<<i))+1);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
string s;
cin >> s;
for (int j = 0; j < N; j++) {
arr[i][j] = s[j]-'0';
}
}
memset(cache, -1, sizeof(cache));
cout << solve(0, 0, 1)+1;
return 0;
}
여담
그림을 여러번 사도 되는 줄 알았는데 아니었다. 문제를 꼼꼼히 읽도록 하자.
Author And Source
이 문제에 관하여(백준 1029번: 그림 교환), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-1029번-그림-교환저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)