백준 - 1029 그림 교환

문제 링크입니다 : www.acmicpc.net/problem/1029

1029번: 그림 교환

DP + 비트마스크 문제였다.

 

문제를 꼼꼼히 안 읽어서 조건을 잘못 파악했었다. 꼼꼼히 읽는 습관을 들여야겠다.

 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int N;

vector<string> adj;

vector<vector<vector<int>>> cache;

int getMaxOwner(int cur, int price, int visited) {
    
    int& ret = cache[cur][price][visited];
    if(ret != -1) return ret;

    visited |= (1 << cur);
    ret = 0;

    for(int i = 0; i < adj.size(); i++) {
        if(cur != i && adj[cur][i] - '0' >= price && ((visited & (1 << i)) == 0)) {
            ret = max(ret, getMaxOwner(i, adj[cur][i] - '0', visited));
        }
    }

    visited ^= (1 << cur);
    ret++;

    return ret;

}

int main() {

    cin >> N;

    cache.assign(N, vector<vector<int>>(10, vector<int>((1 << 15) + 1, -1)));

    for(int i = 0; i < N; i++) {
        string str;
        cin >> str;
        adj.push_back(str);
    }

    cout << getMaxOwner(0, 0, 0);


    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~