[C++] 1006 - 습격자 초라기 (플래티넘3)

1. 문제 설명

 

1006번: 습격자 초라기

---

2. 아이디어

 

문제도 너무 잘 이해되고, 아이디어도 바로바로 떠올라서 뭐지? 싶었는데, 예전에 다른 알고리즘을 검색해보다가 언뜻 봤었던 걸 아직까지 기억하고 있었다...

갑자기 코드 짜다가 생각나서 구글 뒤져봤더니 아니나 다를까 내 아이디어가 아니었다.

차라리 중간에 찾아보지라도 말 걸..ㅠㅠ 그래도 조금 다른 관점으로 흘러가다가 확인해버렸더니 그대로 머리가 굳어버려서 다른 방법을 시도하다가 더 나은 방법이 떠오르질 않아서 포기했다.

그냥 코드 올려놓고 반 년 후 쯤에 다시 보면 기억 말소되어 있을 테니, 그 때 다시 풀어야겠다.

 

백준 1006번

여기저기 찾아보니까 코드의 근원이 이곳인 것 같다. 확실한진 모르겠지만.

 

그렇게 난이도 있는 문제는 아니고, 다만 조건으로 분기점을 나눌 것들이 많아서 정리를 안 하면 코드가 금새 더러워진다.

inner과 outer 라인을 동시에 긁을 건데, 경우의 수는 4가지가 있다.

• 안 묶고 지나치는 경우
• inner 라인만 묶는 경우
• outer 라인만 묶는 경우
• inner라인과 outer라인을 묶거나 or inner 라인 따로 outer 따로 묶이는 경우

4번째에 후자인 경우엔 이전 상태가 안 묶여 있다는 전제 조건이 성립해야 한다.

나머지도 생각해보면 너무 간단하다.

inner를 묶으려면 이전 상태가 inner라인끼리 묶였거나 inner&outer 라인이 묶인 상태가 아니어야 하며,

outer를 묶을 때도 마찬가지다.

 

다만 이 부분이 내 코드에선 조금 더러웠는데 위 블로그에선 엄청 깔끔하게 작성되어 있었다는 차이가 있었다.

덕분에 그래도 인덱스를 이런 식으로 다룰 수도 있겠구나~ 하고 많이 배웠다.

참고로 last를 인자로 보낼 때, idx로 삼항 연산자를 넣는 이유는 이게 원형이다 보니 0번 째 인덱스 기준에서 묶는다는 개념이 들어가면 결국 inner 라인의 경우엔 n-1번째 인덱스와 엮여있다는 말이 된다.

따라서 마지막 라인 상태가 현재 어떤 상태로 존재하는지 판단하기 위해서 따로 체크한 것이다.

 

---

3. 코드

#include <iostream>
#include <algorithm>
#include <cstring>

#define endl "\n"
using namespace std;

int enemy[20005];
int cache[10005][4][4];

int operation(int idx, int prev, int last, int n, int w) {
    int &unit = cache[idx][prev][last];
    bool is_inner, is_outer, is_inner_outer;

    if (unit) return unit;

    is_inner = (enemy[idx] + enemy[idx ? idx-1 : n-1] <= w);
    is_outer = (enemy[idx] + enemy[idx ? 2*idx-1 : 2*n-1] <= w);
    is_inner_outer = (enemy[idx] + enemy[idx+n] <= w);

    if (idx == n-1) {
        if (idx == 0) return is_inner_outer ? 1 : 2;
        unit = 2;
        if (last == 0) {
			if (is_inner && !(prev & 1)) unit = 1;
			if (is_outer && prev < 2) unit = 1;
			if (is_inner_outer) unit = 1;
			if (is_inner && is_outer && prev == 0) unit = 0;
        } else if (last == 1) {
            if (is_outer && prev < 2) unit = 1;
        } else if (last == 2) {
            if (is_inner && !(prev & 1)) unit = 1;
        }
        return unit;
    }

    // bifurcation
    unit = 2 + operation(idx+1, 0, idx ? last : 0, n, w);
    if (is_inner && !(prev & 1))
        unit = min(unit, 1+operation(idx+1, 1, idx ? last : 1, n, w));
    if (is_outer && prev < 2)
        unit = min(unit, 1+operation(idx+1, 2, idx ? last : 2, n, w));
    if (is_inner && is_outer && prev == 0)
        unit = min(unit,   operation(idx+1, 3, idx ? last : 3, n, w));
    if (is_inner_outer)
        unit = min(unit, 1+operation(idx+1, 3, idx ? last : 0, n, w));

    return unit;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t; cin >> t;
    while(t--) {
        memset(cache, 0, sizeof(cache));
        int n, w; cin >> n >> w;

        for (int i=0; i < 2*n; i++) cin >> enemy[i];
        cout << operation(0, 0, 0, n, w) << endl;
    }

    return 0;
}