[백준] 1311 할 일 정하기 1, python, C++

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

1311번: 할 일 정하기 1

어제와 이어서 비트마스크를 사용한 동적 계획법을 공부했다.

문제만 보면 모든 조합 만들어서 최솟값을 찾으면 된다. 그러면 완전탐색이나 백트래킹을 사용해서 탐색을 하면 모든 조합을 찾을수있다. 하지만 N의 최댓값이 20이므로 20^20 이나 20!은 매우 큰 숫자이므로 다른 방법을 찾아야한다.

완전 탐색을 하다보면 항상 겹치는 부분이 생기게 되는데 이때의 값들을 저장하고 일반적인 값을 저장하는게 아닌 열의 상태를 비트마스크로 저장한다면 연산 자체를 줄여서 속도를 높일수 있다.

그러면 열의 상태를 저장하기 위해 어떤 값이 들어가야하는지부터 설정해야한다. 현재 상태에서 일을 이미 하고 있는지를 체크해야하기 때문에 행은 n번째 사람 열은 이전 사람까지 선택한 일을 표현하면 된다. 메모이제이션을 위한 메모리는 sizeof(int) * n * (1<<n)이 된다.

모든 조합을 찾을땐 현재 선택한 사람이 이미 일을 하고 있는 경우(방문 체크를 한 뒤) 값이 저장되어있으므로 그대로 return 해주고, 아닌 경우에만 값을 찾는다. (처음 탐색할땐 걸리지 않지만 일부분이 같은 경우를 탐색할 때 걸리게 되므로 시간을 줄일수 있다.)

 

import sys;input = sys.stdin.readline
INF = 987654321
def dfs(ind, limit, state, memo, d):
    if ind == limit:
        return 0
    if memo[ind][state] != -1: return memo[ind][state]
    memo[ind][state] = INF
    for i in range(limit):
        if state & (1 << i): continue
        next = state | (1 << i)
        memo[ind][state] = min(memo[ind][state], dfs(ind + 1, limit, next, memo, d) + d[ind][i])
    return memo[ind][state]

def main():
    N = int(input())
    d = [list(map(int, input().split())) for _ in range(N)]
    memo = [[-1 for _ in range(1 << N)] for _ in range(N)]
    answer = dfs(0, N, 0, memo, d)
    print(answer)

if __name__ == '__main__':
    main()

#include<iostream>
#include<cstring>
using namespace std;
#define INF 9876543210
int N;
int d[20][20];
int m[29][1 << 20];

int bt(int ind, int limit, int state) {
	if (ind == limit) return 0;
	if (m[ind][state] != -1) return m[ind][state];

	m[ind][state] = INF;
	for (int i = 0; i < limit; i++)
	{
		if (state & (1 << i)) continue;
		int next_state = state | (1 << i);
		int next_val = bt(ind + 1, limit, next_state) + d[ind][i];
		if (next_val < m[ind][state]) {
			m[ind][state] = next_val;
		}
	}
	return m[ind][state];
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> d[i][j];
	memset(m, -1, sizeof(m));
	cout << bt(0, N, 0);

	return 0;
}

---

아마 내일도 비트마스크 + dfs 문제를 풀지 않을까

---

참고

https://technicolour.tistory.com/14

[백준 1311] 할 일 정하기1