boj 17528 Two Machines

www.acmicpc.net/problem/17528

17528번: Two Machines

2019 icpc 지역예선 L번이고, 2020 icpc 예비소집 문제였습니다.

 

icpc 예선 때 그리디로 접근을 해봤을때 WA를 받아서 결국 못풀었는데 이게 dp라고해서 당황했던 기억이 있습니다.....

 

newdeal123.tistory.com/5

[BOJ][백준]DP-17528번 Two Machines

 

이후에 위의 블로그에서 얻은 정보를 바탕으로 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를 재귀로 넘겨줍니다.

 

이 과정을 반복하시면 되겠습니다.

 

시간이 되면 냅색문제 개념부터 차근차근 봐야겠습니다..

 

 

#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;
}