안녕하세요,
재재입니다.
boj 1311 할일 정하기 문제에 대한 솔루션입니다.
BOJ 1311 할일 정하기
(1) 문제 설명
출처: https://www.acmicpc.net/problem/1311
하나의 사람은, 하나의 일을 해야합니다.
최대 20명 이하의 사람이 존재하며,
이 때 모든 일을 끝낼 때 최소의 cost 를 구하는 문제입니다.
(2) TLE 코드
Top-down 방식을 이용해서,
생각할 수 있는 가장 간단한 형태의 점화식입니다.
dp[S][i] : 현재 상태 S이고, i 인덱스 일 때 최적의 코스트
위의 점화식에서 모든 일을 끝마쳤을 때 S의 값은 다음과 같습니다.
$$ S = (2^N) – 1 $$
위의 점화식을 구현하면 시간 복잡도는 다음과 같습니다.
$$ O(SN^2) $$
여기서 S는 bitwise operation 으로 사용해서 나타낼 수 있는 상태의 갯수입니다.
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
int n;
int c[20][20];
int dp[1 << 20][20];
int dy(int S, int i) {
if (S == (1 << n) - 1)return 0;
int &ret = dp[S][i];
if (ret != -1)return ret;
ret = 200001;
for (int j = 0; j < n; j++) {
if (S&(1 << j))continue;
ret = min(ret, c[i][j] + dy(S | (1 << j), j));
ret = min(ret, dy(S, j));
}
return ret;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &c[i][j]);
}
}
memset(dp, 0xff, sizeof(dp));
printf("%d\n", dy(0, 0));
}
위의 코드는 이 문제에서 제한한 1초 안에 나오기가 어렵 기 때문에,
다른 방법이 필요합니다.
(3) 풀이 도출
(2) TLE 코드에서 시간을 가장 많이 잡아 먹는 요인은 바로,
사람의 index 인 i를 정하는 것이었는데요.
사실 사람의 순서는 중요하지 않다는 생각을 한다면,
이 문제의 시간 복잡도를 획기적으로 줄일 수 있습니다.
즉, 사람을 순서대로 넣어주면 더이상 index 를 신경쓰지 않아도 되는데요.
바로 이점 때문에, 이 문제를 1초 안에 해결 할 수 있습니다.
점화식은 다음과 같습니다.
dp[S] : S 상태일 때 최적
이 때, 시간 복잡도는 다음과 같습니다.
$$ O(SN) $$
(4) 정답 코드
BOJ 1311 할일 정하기