백준 1311 할 일 정하기 1
23 Jun 2021https://www.acmicpc.net/problem/1311
n명의 사람과 n개의 일이 있을 때 사람마다 일을 처리하는 비용이 각각 적혀있다고 했을 때 모든 일을 하는데 필요한 비용의 최솟값을 구하는 문제이다. n개의 일에 대해 비트마스크를 적용시켜 상태를 확인한다고 하자. 모든 경우에 대해 탐색해야하기 때문에 dfs를 사용할 것이고 중복 연산을 방지하기 위해 dp를 사용할 것이다.
0번째 사람부터 n-1번째 사람까지 하나씩 일을 부여할 것인데 visited라는 변수를 통해 아직 해결되지 않은 일들을 for문을 통해 다음 사람에게 부여시킨다. for문 내부에서는 dfs를 통해 해당 경우의 최소 비용을 탐색해오고 그 중 가장 적은 비용이 드는 것을 선택한다.
visited를 비트마스크가 아닌 배열로 해도 기능상에는 차이가 없다. 하지만 길이 20의 배열을 계속해서 함수 호출로 넘겨줘야하기 때문에 overhead가 상당하다. 그래서 비트마스크를 활용하는 것이다.
- 전체 코드
let n = Int(readLine()!)!
var dp:[[Int]] = Array(repeating: Array(repeating: -1, count: 1<<21), count: 20)
var cost:[[Int]] = []
for _ in 1...n {
cost.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}
func dfs(d: Int, visited: Int) -> Int {
if d == n {
return 0
}
else if dp[d][visited] != -1 {
return dp[d][visited]
}
else {
dp[d][visited] = 1_000_000
for i in 0..<n {
if (visited & (1<<i)) == 0 {
dp[d][visited] = min(dp[d][visited], dfs(d: d+1, visited: visited|(1<<i)) + cost[d][i])
}
}
return dp[d][visited]
}
}
print(dfs(d:0, visited:0))