[백준] 1311번: 할 일 정하기 1 (C++)

문제 링크

1311번: 할 일 정하기 1

---

요새 DP 문제에 빠져 있습니다.... 바텀업 DP부터 트리DP까지 공부하고 있는 도중,

예전에 외판원 순회 문제를 풀면서 접하게 되었던 비트마스크를 이용한 DP 문제를 우연히 보게 되었습니다!

이번 문제는 비트를 어떻게 이용하는지만 블로그를 참고했고, 문제풀이는 스스로 생각해서 풀(어서 뿌듯했)었습니다.

같이 풀이를 살펴보시죠! 😄

풀이

비트마스크를 이용한 DP로 풀이하면 됩니다.

이 문제를 풀 수 있으면, 외판원 순회 문제도 도전해 보실 수 있을 겁니다!

일단 문제 풀이 전에 비트마스크에 대한 설명을 해드리겠습니다.

비트마스크를 이용하려면, 비트 연산자와 시프트 연산자에 대해서 알아야 하고,

그 연산자들을 이용해서 비트를 확인하고 활성화하고 비활성화하는 방법을 알아야 할 것입니다.

저희는 `&`, `|`, `<<`, `>>` 연산자를 사용해서 DP 배열을 비트처럼 다룰 것입니다.

• `&` : AND 연산자
• `|` : OR 연산자
• `<<` : 왼쪽 시프트 연산자 (예: 1 << 3 == \(2^3\) == 8 == 2진수 비트로 1000)
• `>>` : 오른쪽 시프트 연산자 (예: 8 >> 2 == \(2\) == 2진수 비트로 10)

이 연산자들을 활용하면 다음과 같은 응용 연산이 가능해집니다.

• 주어진 비트의 n번째 비트가 1인지 확인하는 연산 : \( bit \ \& \ (1 << n) \)
• 주어진 비트의 n번째 비트를 1로 만드는 연산 : \( bit \ \| \ (1 << n) \)
• 주어진 비트의 n번째 비트를 0으로 만드는 연산 : \( bit \ \| \ !(1 << n) \)

이 응용 연산들을 이용해서, Top-Down(재귀) DP를 구현하여 풀이를 진행하면 됩니다.

우리가 풀 문제에서 비트마스크는 i번째 사람이 j번째 일을 하는 상태를 저장하게 됩니다.

비트마스크는 그림으로 그리면 다음과 같이 그려질 것입니다. (5개 일이 있다고 가정)

간소화하여 일부만 그렸습니다.

처음에  bit는 `0`부터 시작하고, 반복문을 돌며 비트를 활성화하면서

dp[해당 비트의 값] = 이때까지 일한 비용들의 합의 최솟값을 더해주면 됩니다.

풀이코드

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int n;
int d[21][21];
int dp[(1 << 21) + 1];

int rec(int k, int bit) {
  if (k > n) return 0;
  if (dp[bit]) return dp[bit];

  dp[bit] = 1e9;
  for (int i = 1; i <= n; i++) {
    if (bit & (1 << i)) continue;
    dp[bit] = min(dp[bit], rec(k + 1, bit | (1 << i)) + d[k][i]);
  }

  return dp[bit];
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> d[i][j];
    }
  }

  cout << rec(1, 0);
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

최종적으로 모든 일을 하는 비트열(`k > n`)은 0입니다. 왜냐하면 트리의 리프노드이어서 더이상 진행할 일이 없기 때문입니다.

 

 

배운점

• 비트마스킹을 이용한 DP에 대해 이해하게 되었습니다.
• Top-down DP를 복습할 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!