취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18559번 문제인 부모님께 큰절 하고이다.
문제는 아래 링크를 확인하자.

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

이 문제에서는, 주어진 N개의 수로 어떤 1<k<N에 대하여 첫번째부터 k번째 수까지는 감소하는 등차수열, k번째부터 N번째 수까지는 증가하는 등차수열이 되게 할 수 있는지의 여부를 묻고 있다.

위와 같이 수들을 배치할 수 있다면 k번째 수는 N개의 수중 가장 작은 수일 수밖에 없다는 점을 확인하자.

또한, 두번째로 작은 수가 등차수열의 일부이려면 그 수와 가장 작은 수와의 차이만큼이 공차인 등차수열이 하나 있어야하므로, 가장 작은 수가 초항, 두번째로 작은 수가 두번째 항인 (중간에 항이 빠지지 않은) 등차수열에 해당하는 수를 N개의 수에서 지울 수 없을 때까지 지워나가자. 단, 마지막으로 지워진 수는 또다른 등차수열에 포함시켜서 이어나갈 가능성이 있으니 일단 저장해두자.

가장 작은 수와 두번째로 작은 수가 같다면, 공차가 0이므로 조건에 맞는 수열을 만들 수 없다는 점에 신경쓰자.

이제 남은 수가 (마지막으로 지워진 수)를 포함하거나 포함하지 않은 상태로 등차수열을 이룬다면 "Yes", 아니면 "No"를 출력하면 문제를 해결할 수 있다. (이것의 증명은 간단하므로 생략한다.)

글쓴이는 multiset 자료구조를 이용하여 문제를 해결하였으나, 더 좋은 방법이 있을 거라고 생각된다.

아래는 제출한 소스코드이다.

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

multiset<int> st;

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

    int N; cin >> N;
    while (N--) {
        int x; cin >> x;
        st.insert(x);
    }

    int bottom = *st.begin();
    st.erase(st.begin());
    int diff = *st.begin() - bottom;
    int current = *st.begin();

    if (diff == 0) {
        cout << "No";
        return 0;
    }

    int lastdeleted;
    while (!st.empty()) {
        auto iter = st.find(current);
        if (iter != st.end()) {
            st.erase(iter);
            lastdeleted = current;
            current += diff;
        }
        else break;
    }

    if (st.empty()) {
        cout << "Yes";
        return 0;
    }
    else if (st.size() == 1) {
        cout << "Yes";
        return 0;
    }

    diff = *st.begin() - bottom;
    current = *st.begin();

    int cnt = 0;
    while (!st.empty()) {
        auto iter = st.find(current);
        if (iter != st.end()) {
            current += diff;
            cnt++;
        }
        else break;
    }

    if (cnt == st.size()) {
        cout << "Yes";
        return 0;
    }
    
    st.insert(lastdeleted);
    diff = *st.begin() - bottom;
    current = *st.begin();
    cnt = 0;
    while (!st.empty()) {
        auto iter = st.find(current);
        if (iter != st.end()) {
            current += diff;
            cnt++;
        }
        else break;
    }

    if (cnt == st.size()) cout << "Yes";
    else cout << "No";
}