[백준/C++] 27893 특별한 드롭킥

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

27893번: 특별한 드롭킥

조금 까다로웠던 문제. 맞왜틀

어떻게 풀어야 할지는 생각했는데, 그게 코드를 구현하는 관점에서는 조잡한 풀이여서 오래 걸린 것 같다. 다 풀고 나서 다른 코드들을 보니 확실히 그런 생각이 들었다.

 

그럼 시작!

 

동호가 장애물을 놓는 경우는 크게 두 가지로 나눌 수 있다.

 

1. 장애물 옆에 놓는다 ..XX..

2. 장애물만 덩그러니 놓는다. ..X...X

 

조금 더 확장하면 다음과 같다.

 

1-1. 장애물을 놓다가 이어지는 경우 XXXXXX

1-2. 그냥 장애물만 슥 추가된 경우 XXX.XX

 

2-1. 하나만 놓은 경우 ...X...

2-2. 여러 개를 놓은 경우 ...XXX.

 

각각의 경우에 대해 절약되는 시간을 생각해 보면

 

1-1. (사이에 놓은 장애물 수 + 2)

1-2. (놓은 장애물 수)

2-1. (오히려 손해 -1)

2-2. (놓은 장애물 수 - 2)

 

이므로 1-1 > 1-2 > 2-2 순으로 놓는 것이 이득인 것을 알 수 있다.

요약하자면 이렇다.

 

- 장애물이 있다면 사이에 놓거나 옆에 놓는다

- 장애물이 없다면 놓을 수 있는 장애물이 3개 이상인 경우에만 이어서 놓는다

 

코드 구현 과정 1

원래 코드는 조금 복잡했다.

 

1. 장애물들의 간격을 구한다(반복문)

2. 장애물을 놓는다(반복문)

3. 복도를 걸어간다(반복문)

 

여러 개의 간격이 존재할 경우 가장 작은 것부터 시작해서 최대한 많이 잇는 것이 이득이므로 pq를 사용했다.

이 코드의 비효율적인 점은 2에서 기인한 것이었는데,

이걸 구현하기 위해서 1에서는 간격과 좌표를 같이 저장하느라 메모리가 2배로 들었다.

물론 복도의 구조도 기억해야 장애물을 놓을 수 있으므로 그만큼의 배열도 사용해야 했다.

놓을 장애물이 남았는데 간격이 없는 경우도 굳이 생각해서, 반복문을 여러 번 돌면서 위치를 일일이 찾아서 놓도록 구현했었다(...)

장애물을 효율적으로 놓은 다음 걸어가야 하니까 마지막에 반복문을 또 돌았다.

 

결론적으로 메모리는 메모리대로, 시간은 시간대로 잡아먹는 코드였다.

 

#include <iostream>
#include <queue>

using namespace std;

struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        if (a.first == b.first)
            return a.second < b.second;
        return a.first > b.first;
    }
};

char path[200001];
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
int ans = 0;
int obstacle = 0;

int main() {
    int n, m;
    cin >> n >> m;

    int start = 0;
    int tmp = 0;
    for (int i = 1; i <= n; i++) {
        cin >> path[i];
        if (path[i] == 'X')
            obstacle++;
        if (tmp) {
            if (path[i] == '.')
                tmp++;
            else {
                pq.push({ tmp, start });
                tmp = 0;
            }
        }
        if (path[i] == '.' && path[i - 1] == 'X') {
            start = i;
            tmp++;
        }
    }

    if (tmp)
        pq.push({ tmp, start });

    while (!pq.empty()) {
        tmp = pq.top().first;
        start = pq.top().second;
        if (tmp <= m) {
            for (int i = 0; i < tmp; i++)
                path[start + i] = 'X';
            m -= tmp;
        }
        else
            break;
        pq.pop();
    }

    if (m) {
        if (!obstacle) {
            if (m >= 2) {
                for (int i = 1; i <= m; i++)
                    path[i] = 'X';
            }
        }
        else {
            if (!pq.empty()) {
                tmp = pq.top().first;
                start = pq.top().second;
                for (int i = 0; i < tmp; i++) {
                    path[start + i] = 'X';
                    m--;
                    if (!m)
                        break;
                }
            }
            else {
                start = 1;
                if (path[1] == '.') {
                    for (int i = 2; i <= n; i++) {
                        if (path[i] == 'X') {
                            start = i;
                            break;
                        }
                    }
                    start--;
                    for (; start >= 1; start--) {
                        path[start] = 'X';
                        m--;
                        if (!m)
                            break;
                    }
                }

                if (path[n - 1] == '.') {
                    for (int i = n - 2; i >= 1; i--) {
                        if (path[i] == 'X') {
                            start = i;
                            break;
                        }
                    }
                    start++;
                    for (; start < n; start++) {
                        if (!m)
                            break;
                        path[start] = 'X';
                        m--;
                    }
                }
            }
        }
    }

   /* for (int i = 1; i <= n; i++)
        cout << path[i];
    cout << endl;*/
    bool x = false;
    for (int i = 1; i <= n; i++) {
        if (!x) {
            if (path[i] == 'X') {
                //cout << i << path[i] << '\n';
                x = true;
            }
            else
                ans++;
        }
        else {
            if (path[i] == '.') {
                ans += 3;
                x = false;
            }
        }
    }
    if (x)
        ans += 2;
    cout << ans;
    return 0;
}

 

상당히 난잡한 걸 알 수 있다.

당연히 틀렸다.

 

코드 구현 과정 2

여기부터는 위의 코드를 보고, 머릿속에서 엉켜 있던 것을 네 가지 경우로 구체화하는 과정에서 정리된 것들이다.

 

1. 반복문을 너무 많이 돈다 -> 합치자!

2. 장애물을 놓는 것은 사칙연산으로 처리할 수 있다 -> 미리 걸어간 셈 치고 절약된 시간만 빼면 된다

 

이제 동작은 다음과 같다.

 

1. 장애물의 간격을 구하면서 전체 시간을 계산한다

2. 장애물을 놓음으로써 절약되는 시간을 뺀다

 

사실상 복도를 먼저 걷고 장애물을 놓는 느낌과 비슷하다. 뭔가 어제의 커피와는 반대인 느낌...ㅎㅎ

장애물을 놓기 위한 좌표를 알 필요가 없으므로 pq에는 간격만 저장하면 된다.

복도를 걸어가면서 시간을 계산하는 것도 그냥 입력과 동시에 처리할 수 있으니 복도 배열이 필요없다.

 

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
int ans = 0;
int obstacle = 0;

int main() {
    int n, m;
    cin >> n >> m;

    int cnt = 0;
    char c;
    bool x = false;
    for (int i = 1; i <= n; i++) {
        cin >> c;
        if (c == 'X') {
            obstacle++;
            x = true;
            if (cnt) {
                pq.push(i - cnt);
                cnt = 0;
            }
        }
        else {
            if (x) {
                cnt = i;
                ans += 3;
                x = false;
            }
            else
                ans++;
        }
    }
    if (x)
        ans += 2;

    while (!pq.empty()) {
        cnt = pq.top();
        if (cnt <= m) {
            m -= cnt;
            ans -= (cnt + 2);
        }
        else
            break;
        pq.pop();
    }

    ans -= (!obstacle ? (m >= 3 ? m - 2 : 0) : m);

    cout << ans;
    return 0;
}

 

그래도 여전히 다른 코드에 비해 시간이 많이 들긴 한다!