17528번: Two Machines
스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나
www.acmicpc.net
2019 icpc 지역예선 L번이고, 2020 icpc 예비소집 문제였습니다.
icpc 예선 때 그리디로 접근을 해봤을때 WA를 받아서 결국 못풀었는데 이게 dp라고해서 당황했던 기억이 있습니다.....
[BOJ][백준]DP-17528번 Two Machines
https://www.acmicpc.net/problem/17528 17528번: Two Machines 문제 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각..
newdeal123.tistory.com
이후에 위의 블로그에서 얻은 정보를 바탕으로 2020년 icpc 예비소집때는 AC를 받을 수 있었습니다!
하지만 냅색방법으로 푸는 것이 효율이 더 좋다고 합니다.
저는 냅색을 잘 이해하지 못해서 이해하는데 성공했던 이 방법으로 하였습니다.
우선 dp의 구성은
dp[index][해당 기계의 현재 남은 작업량][A기계 or B기계] => 최소시간
이렇게 하였습니다.
만약 A 기계가 now만큼의 작업을 수행중일 때 3가지를 고려하여야 합니다.
1. 다음 작업을 A기계가 수행하는 경우
=> 그냥 A의 작업량을 추가하면 됩니다.
2. 다음 작업을 B기계가 수행하는 경우 & now보다 다음 작업량이 많을 경우
=> 작업이 B로 넘어가며, now만큼의 작업을 수행한 후에 next - now를 재귀로 넘겨줍니다.
3. 다음 작업을 B기계가 수행하는 경우 & now보다 다음 작업량일 적을 경우
=> 그대로 A가 작업하며, now-next를 재귀로 넘겨줍니다.
이 과정을 반복하시면 되겠습니다.
시간이 되면 냅색문제 개념부터 차근차근 봐야겠습니다..
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 1000000000
using namespace std;
int dp[251][62501][2];
int list1[251], list2[251], N;
int func(int idx, int now, int t) {
if (idx == N + 1) return now;
if (dp[idx][now][t] != -1) return dp[idx][now][t];
dp[idx][now][t] = INF;
if (t) {
dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, now + list1[idx], t));
if (now < list2[idx]) {
dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, list2[idx] - now, 1 - t) + now);
}
else {
dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, now - list2[idx], t) + list2[idx]);
}
}
else {
dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, now + list2[idx], t));
if (now < list1[idx]) {
dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, list1[idx] - now, 1 - t) + now);
}
else {
dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, now - list1[idx], t) + list1[idx]);
}
}
return dp[idx][now][t];
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> list1[i] >> list2[i];
}
memset(dp, -1, sizeof(dp));
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
cout << func(1, 0, 0) << '\n';
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 5557 1학년 (0) | 2021.02.05 |
|---|---|
| boj 5573 산책 (0) | 2021.02.04 |
| boj 9657 돌 게임 3 (0) | 2021.01.27 |
| boj 2096 내려가기 (0) | 2021.01.22 |
| boj 1103 게임 (0) | 2021.01.22 |