[BOJ] 할 일 정하기 1

할 일 정하기 1

TimeLimit	MemoryLimit	Condition	TAG
1s	512MB	1 ≤ N ≤ 20, 1 ≤ b ≤ 10,000	Dynamic Programming

그냥 바로 풀었던 dp 중 하나인 것 같습니다. 냄새가 너무 심하게나서 바로 bit mask로 접근했던거 같구요.(아마 최근에 bit mask를 많이 풀어서 바로 했던거 같아요)

재미있게 풀었던 문제였습니다.

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <math.h>
using namespace std;
using ll = unsigned long long;
using ld = long double;
//ll MOD = 1'000'000'007;
ll MOD = 1'000'000'000;
//ll MOD = 1.8446744074E19;

int N;

int costs[21][21];

ll dp[1 << 20];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++) cin >> costs[i][j];
    }
    
    for(int i = 0; i < 1 << 20; i++) dp[i] = LLONG_MAX;
    dp[0] = 0;
    for(int i = 1; i < 1 << 20; i++){
        
        int idx = -1;
        for(int j = 0; j < 20; j++) idx += (i & (1 << j)) ? 1 : 0;
        
        for(int j = 0; j < 20; j++){
            int current = (1 << j);
            if(!(i & current)) continue;
            
            int next = i - current;
            
            dp[i] = min(dp[next] + costs[idx][j], dp[i]);
            
        }
    }
    
    
    cout << dp[(1 << N) - 1];
    
    


    return 0;
}