8. dp - 토글링, 역추적

8.md

0.00MB

0. 복습

우선 오늘 배울 것은 dp개념이 잡혀있지 않다면, 필요가 없다. dp를 조금 풀고 와서 하는게 좋다.

1. 토글링

현재까지, 대부분의 문제는 128MB 이상의 넉넉한 메모리 제한을 갖고 있다.

따라서 배열의 크기를 별로 상관하지 않고 문제를 풀 수 있었다.

하지만, 출제자가 의도적으로 메모리 제한을 굉장히 낮게 한다면, 우리는 머리를 조금 더 써야한다.

바로 여기서 토글링의 개념이 나온다.

이전값, 현재값, 다음값 이 세가지 값 외에 다른값은 쓰이지 않을 때, 우리는 토글링을 사용하여 배열을 축소할 수 있다.

2의 나머지의 성질을 이용하여 [i%2]의 값을 이용하여 [(i+1)%2)]의 값을 채우고, 그 다음엔 (i+2)%2 == i%2 이므로 다시 [i%2]의 값을 채우면 되는것이다.

참고 문제 : boj.kr/2096

2. 역추적

dp를 저장할 때 어떤 값에서 변화되었는지 따로 다른 배열에 저장해두는 것을 말한다. 따로 정형된 알고리즘은 없고, 직접 머리를 써서 역추적을 하면 된다.

참고 문제 : boj.kr/2655

99. 부록 : 참고 문제 풀이

• boj.kr/2096

#include <iostream>
using namespace std;
int mindp[2][3], maxdp[2][3];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        int a, b, c; cin >> a >> b >> c;
        maxdp[(i+1)%2][0]=max(maxdp[i%2][0], maxdp[i%2][1])+a;
        mindp[(i+1)%2][0]=min(mindp[i%2][0], mindp[i%2][1])+a;

        maxdp[(i+1)%2][1]=max(maxdp[i%2][0], max(maxdp[i%2][1], maxdp[i%2][2]))+b;
        mindp[(i+1)%2][1]=min(mindp[i%2][0], min(mindp[i%2][1], mindp[i%2][2]))+b;

        maxdp[(i+1)%2][2]=max(maxdp[i%2][2], maxdp[i%2][1])+c;
        mindp[(i+1)%2][2]=min(mindp[i%2][2], mindp[i%2][1])+c;
    }
    cout << max(maxdp[N%2][0], max(maxdp[N%2][1], maxdp[N%2][2])) << " " << min(mindp[N%2][0], min(mindp[N%2][1], mindp[N%2][2])) << '\n';
}

• boj.kr/2655

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
typedef struct block {
    int idx;
    int area;
    int height;
    int weight;
} BLOCK;
bool cmp(BLOCK a, BLOCK b){
    return a.area<b.area;
}
BLOCK arr[100];
int dp[100];
int memory[100];
int main(){
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i].area >> arr[i].height >> arr[i].weight;
        arr[i].idx = i+1;
    }
    sort(arr, arr+N, cmp);
    pair<int, int> res;
    res.first = 0;
    res.second = 0;
    for(int i=0; i<N; ++i){
        int maxArrIdx=-1;
        dp[i]=arr[i].height;
        for(int j=0; j<i; ++j){
            if(arr[j].weight < arr[i].weight) { // area는 이미 검사함.
                if(dp[i] < dp[j]+arr[i].height) {
                    dp[i]=dp[j]+arr[i].height;
                    maxArrIdx = j;
                }
            }
        }
        memory[i]=maxArrIdx;
        if(dp[i]>res.first) {
            res.first = dp[i];
            res.second = i;
        }
    }
    stack<int> stk;
    int k=res.second;
    while(1) {
        stk.push(arr[k].idx);
        if(memory[k]==-1) break;
        k=memory[k];
    }
    cout << stk.size() << '\n';
    while(!stk.empty()) {
        cout << stk.top() << '\n';
        stk.pop();
    }
}