[C++] 1311번 할 일 정하기 1 - DP, 비트마스킹, 비트필드를 이용한 DP

1. 문제

• N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명이다. 또한 모든 사람은 모든 일을 할 능력이 있다.
• 사람과 일은 1~N까지 번호가 매겨져 있다.
• 모든 일을 하는데 필요한 비용의 최솟값을 구하자.

<입력>

• - 1 -   사람과 일의 수 \(N(1 \leq N \leq 20)\)
• - N개의 줄 -   비용 \(D(1 \leq D \leq 10,000)\)

<출력>

• 모든 일을 하는데 필요한 비용의 최솟값

2. 재정의

• X

3. 해결 방법

• 비트필드를 이용한 DP 기본 문제

4. 실수한 점, 개선 방법

• 얘는 비트필드를 이용할 때 DP에서 탐색하는 no와 상관없이 dp가 같기 때문에 통일해도 된다.
• 이렇게 푼 다른 사람 코드가 있어서 아래에 링크해두었다.

 

<코드>

#include <iostream>

using namespace std;

const int MAX_N = 21;
const int INF = 987654321;

// <문제>
// 사람과 일의 수 N
int N;
// 일을 하는데 필요한 비용 D
int D[MAX_N][MAX_N];

// DP
int dp[MAX_N][1 << MAX_N];

void input() {
    cin >> N;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> D[i][j];
}

// 비트월드를 이용한 DP
int DP(int now, int visited) {
    // 모든 일을 다 배정했을 경우 반환
    if(now == N)
        return 0;
    
    // 현재 상태를 이미 계산한 값이 dp 테이블에 있다면 그대로 사용
    if(dp[now][visited])
        return dp[now][visited];
    
    for(int i=0; i<N; i++) {
        // 이미 방문한 경우 패스
        if(visited & (1 << i))
            continue;
            
        // i번 노드 방문 처리 후 최소 비용 반환
        int tmp = DP(now+1, visited | 1 << i);
        if(dp[now][visited])
            dp[now][visited] = min(dp[now][visited], D[now][i] + tmp);
        else
            dp[now][visited] = D[now][i] + tmp;
        
        //cout << now << ' ' << i << ' ' << dp[now][visited] << ' ' << visited << '\n';
    }
    
    // 최소 비용 반환
    return dp[now][visited];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    cout << DP(0, 0);
    
    return 0;
}

 

<참고한 코드 (풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/46827763

로그인

 

<외판원 순회 문제>

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-%EB%AC%B8%EC%A0%9C

[알고리즘] 외판원 순회 문제

 

<문제 바로가기>

https://www.acmicpc.net/problem/1311

1311번: 할 일 정하기 1

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.