[1일 1알고] S2 2232 지뢰

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

 

지뢰는 연속으로 터질 수 있으며 Pi를 "초과"하는 힘을 받으면 터집니다.

 

따라서 저는 충격강도가 높은 지뢰는 충격강도가 낮은 지뢰로 절대 터트릴 수 없기 때문에 

충격 강도가 높은 지뢰 순으로 정렬 후 인덱스를 통해 체크해보며 계산했습니다.

---

1.

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;


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

    int N;
    cin >> N;

    vector<pair<int, int>> v(N);
    vector<int> mines(N);

    for (int i = 0; i < N; ++i)
    {
        cin >> v[i].first;
        v[i].second = i;
        mines[i] = v[i].first;
    }

    sort(v.rbegin(), v.rend());

    int cnt = 0;
    int size_idx = 0;
    vector<bool> visited(N, false);
    vector<int> result;
    while (cnt < N)
    {
        int mine_idx = v[size_idx].second;
        if (!visited[mine_idx])
        {
            visited[mine_idx] = true;
            result.push_back(mine_idx + 1);
            ++cnt;

            int strength = v[size_idx].first;
            for (int i = mine_idx - 1; i >= 0; --i) // left
            {
                if (strength > mines[i] && !visited[i])
                {
                    visited[i] = true;
                    strength = mines[i];
                    ++cnt;
                }
                else
                {
                    break;
                }
            }

            strength = v[size_idx].first;
            for (int i = mine_idx + 1; i < N; ++i) // left
            {
                if (strength > mines[i] && !visited[i])
                {
                    visited[i] = true;
                    strength = mines[i];
                    ++cnt;
                }
                else
                {
                    break;
                }
            }
        }
        ++size_idx;
    }

    sort(result.begin(), result.end());

    for (auto elem : result)
        cout << elem << '\n';
    return 0;
}

 

먼저 index 용으로 사용할 벡터와 원복 벡터를 준비하고 충격 강도 순으로 정렬합니다.

이후 정렬한 벡터를 순회하며 지뢰를 직접 터트리는 결과를 계산했습니다.

 

그리고 마지막으로 결과에 대해 정렬했습니다.

---

2.

위의 코드도 정답이지만 더 쉽게 풀 수 있는 방법이 있을 것이라고 생각했습니다.

그러고보니 연쇄적으로 터지는 지뢰의 힘의 크기는 초기의 힘이 아니라 터지는 지뢰의 힘이기 때문에

왼쪽 지뢰의 힘과 오른쪽 지뢰의 힘이 현재 위치의 지뢰의 힘보다 작다면 반드시 직접 터트려야하는 것을 알게되었습니다.

 

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

    int N;
    cin >> N;

    vector<int> v(N);
    for (int i = 0; i < N; ++i)
        cin >> v[i];

    for (int i = 0; i < N; ++i)
    {
        if ((i == 0 || v[i] >= v[i - 1]) &&
            (i == N - 1 || v[i] >= v[i + 1]))
        {
            cout << i + 1 << '\n';
        }
    }



    return 0;
}

 

이를 이용해 만드니 코드가 훨씬 간단해졌습니다.

---

다만 N이 최대 5만이라 그런지 시간 자체는 그게 그거네요

메모리를 아껴서 그래도 좋습니다