[C++] Φ² (백준 30885번)

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

 

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

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

    list<pair<long long, int>> li;
    int n;
    cin >> n;
    for (int i = 1; i < n + 1; i++) {
        int x;
        cin >> x;
        li.emplace_back(x, i);
    }

    while (li.size() > 1) {
        for (auto i = li.begin(); i != li.end(); i++) {
            long long a = i->first; // 현재 가리키고 있는 미생물의 크기
            long long newa = a; // 새로운 미생물의 크기 (흡수 후)

            // 첫 번째 미생물이 아닐 때만
            if (i != li.begin()) {
                auto prev_i = prev(i);
                // 바로 앞 미생물이 작거나 같으면
                if (prev_i->first <= a) {
                    newa += prev_i->first;
                    // i는 계속 현재 미생물을 가리키도록 유지
                    i = li.erase(prev_i);
                }
            }

            // 마지막 미생물이 아닐 때만
            if (next(i) != li.end()) {
                auto next_i = next(i);
                // 바로 뒤 미생물이 작거나 같으면
                if (next_i->first <= a) {
                    newa += next_i->first;
                    // i는 계속 현재 미생물을 가리키도록 유지
                    i = li.erase(next_i);
                    i--;
                }
            }

            // 미생물의 크기 갱신
            i->first = newa;
        }
    }

    auto ans = li.begin();
    cout << ans->first << '\n' << ans->second << '\n';
}

우선 모든 미생물을 연결 리스트에 담는다. first에는 미생물의 크기를, second에는 미생물의 초기 위치를 넣었다. 

그 후 미생물이 한 마리만 남을 때까지 다음을 반복한다. 

1. 앞에 미생물이 존재할 경우, 바로 앞 미생물이 작거나 같으면 흡수한다. 이 때, 바로 앞 미생물의 바로 다음 미생물이 현재 미생물이므로 i는 erase에서 그대로 받는다.

2. 뒤에 미생물이 존재할 경우, 바로 뒤 미생물이 작거나 같으면 흡수한다. 이 때, 바로 뒤 미생물의 바로 다음 미생물은 현재 미생물 기준 바로 뒤 미생물이 되므로 i는 erase에서 받은 후 1을 빼준다.

3. 미생물의 크기를 흡수 후의 크기로 갱신해준다.

 

* erase 함수는 list에서 해당 iterator 위치의 원소를 삭제하고 원래 위치의 다음 원소의 iterator를 반환한다. 

* prev 함수는 list에서 해당 iterator 위치의 원소의 바로 앞 원소의 iterator를 반환한다.

* next 함수는 list에서 해당 iterator 위치의 원소의 바로 뒤 원소의 iterator를 반환한다.

* prev, next 함수를 사용할 때는 범위가 벗어나 정의되지 않은 동작(Undefined Behavior)이 발생하지 않도록 주의해야 한다. 

 

---

 

처음 풀어보는 연결 리스트 문제. C++에서 list를 아예 처음 써보는 것 같다. 

그래서 좀 어려웠지만 C++ STL list에 대해서 이것 저것 배울 수 있어서 유익했다.

 

[참고] https://blog.naver.com/jinhan814/222508424732