[C++] 수위 아저씨의 고민 (백준 9048번)

https://www.acmicpc.net/problem/9048

 

#include <iostream>
#include <vector>
using namespace std;

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

    int t;
    cin >> t;
    
    while (t--) {
        int f, r, n;
        cin >> f >> r >> n;

        int ans = 2 * f + (r + 1);
        vector<int> up(f + 1, 0);
        vector<int> down(f + 1, r + 1);

        for (int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            if (b <= (r / 2)) up[a] = max(up[a], b);
            else down[a] = min(down[a], b);
        }

        for (int i = 1; i <= f; i++) {
            ans += 2 * up[i];
            ans += 2 * (r + 1 - down[i]);
        }

        cout << ans << '\n';
    }
}

처음에는 각 층별로 왼쪽 엘베와 더 가까운 사무실은 왼쪽으로 올라가면서 끄고 오른쪽 엘베와 더 가까운 사무실은 오른쪽으로 내려가면서 끄는게 최적이라고 생각했다. 그래서 각 층별로 왼쪽에 더 가까운 사무실 중 가장 먼 사무실까지의 거리와 오른쪽에 더 가까운 사무실 중 가장 먼 사무실까지의 거리의 합을 ans에 더해주었다. 제출하면 1%도 안 오르고 바로 틀렸다고 뜬다. (WA)

 

- o o o x -

이런식으로 불이 켜져 있는 경우가 반례이다.

이런 경우에는 올라가면서 왼쪽에서 2번 사무실까지 간 다음에 내려가면서 오른쪽에서 3번 사무실까지 가야 한다. 해당 층에서 이동 거리는 8이다. 

하지만, 올라가면서 왼쪽에서 3번 사무실까지 간 다음에 내려올 때는 그냥 내려오는 것이 더 최적이다. 이렇게 이동하면 해당 층에서 이동 거리는 6이다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int t;
    cin >> t;
    
    while (t--) {
        int f, r, n;
        cin >> f >> r >> n;

        int ans = 2 * f + (r + 1);
        vector<vector<int>> o(f + 1, vector<int>());

        for (int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            o[a].push_back(b);
        }

        for (int i = 1; i <= f; i++) {
            o[i].push_back(0);
            o[i].push_back(r + 1);
            sort(o[i].begin(), o[i].end());

            int tmp = 1000;
            int os = o[i].size();
            for (int j = 1; j < os; j++) {
                tmp = min(tmp, 2 * (o[i][j - 1] + r + 1 - o[i][j]));
            }
            ans += tmp;
        }

        cout << ans << '\n';
    }
}

각 층별로 어느 사무실까지는 왼쪽에서 가고 어느 사무실부터는 오른쪽에서 갈건지를 선택해야 한다. 이전에는 그걸 딱 절반으로만 나눠서 틀린 것이었다. 하지만 그건 항상 최적이 아니기에, 각 층별로 모든 조합을 살펴보며 뭐가 최적인지 찾아야 한다. 

구체적인 구현 방법은 이러하다. 각 층별로 불이 켜져 있는 사무실의 번호를 배열에 넣어두고 정렬한다. 그 후, 앞에서부터 두 개씩 보면서 어디서 끊는 것이 이동 거리가 최소가 되는지 구한다. 즉, 어디까지 올라가면서 갈 것이고 어디부터 내려가면서 갈 것인지 정하는 것이다. 그리고 그렇게 구한 층별 최소 이동 거리를 ans에 더한다. (AC)

 

태그가 그리디랑 브루트포스이다. 각 층별로 최적의 선택을 해야한다는 점에서 그리디이고, 하나의 층 안에서는 모든 조합을 따져야 한다는 점에서 브루트포스인 듯하다.

 

---

 

[참고] https://zyos.tistory.com/25

마라톤으로 나온 문제였는데, 이거 푼 사람도 많지 않고 질문 게시판에도 글이 별로 없고 구글링도 진짜 안 나오길래 정말.. 너무 힘들고 절망적이었다. 그러다가 발견한 빛과 같은 지호님의 글... 진짜 이거 아니었음 머리털 다 뽑힐 뻔했다.

나는바보다 나는바보다 나는바보다 나는바보다  나는바보다 나는바보다  나는바보다 나는바보다  나는바보다 나는바보다