[C++] 체인 (2785번)

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

2785번: 체인

---

문제풀이

그리디 쉽지않다. 코드는 정말 간단한데 구현 과정을 생각하는게 어렵다.

 

고려해야 할 점은, 1 1 1같이 주어 졌을 때 하나의 고리만 열면 모든 체인이 연결된다는 점이다. 즉 체인의 고리를 모두 소모하는 경우 연결해야 할 체인이 하나 줄어든다는 점이 핵심이다.

 

받은 입력을 정렬해서, 가장 짧은 체인의 고리를 하나씩 떼서 가장 긴 두 체인을 연결하는데 사용하는 방법을 생각했다.

만약 가장 짧은 체인을 다 쓴다면 그 값을 제거해주면 되고, 뒤에서 부터 가장 긴 체인 두개씩 연결하다 보면 체인이 하나가 될것이라고 생각했다. 즉 배열의 길이가 1이 될것이라고 생각했다.

하지만 이 때 주의할 점이, 만약 지금 배열의 길이가 2이고 짧은 체인이 사라질 경우, 뒤의 두개를 꺼내오는 것이 불가능하다. 그러므로 배열에 체인이 2개 남을 때 까지만 반복문을 돌게 하면 되겠다고 생각했다.

 

그래서 deque를 사용했다. 맨 앞의 체인 고리를 다 빼쓰면 앞의 값을 pop 해주고, 두개 연결 할 땐 뒤의 값 두번 pop해주면 된다고 생각했다.

 

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    deque<int> v(n);
    for(int i=0; i<n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    int answer = 0;
    // 체인이 두개가 될 때 까지, 가장 짧은 체인의 고리를 빼서 가장 긴 두 체인을 합친다.
    while(v.size()>2) {
        v[0]--;
        if(v[0] == 0) v.pop_front();
        int a = v.back();
        v.pop_back();
        int b = v.back();
        v.pop_back();
        v.push_back(a + b + 1);
        answer++;
    }
    if(v.size() == 2) cout << answer + 1;
    else cout << answer;

    return 0;
}

 

다 풀고 다른 사람들 풀이를 보니, 배열의 길이를 사용하지 않아도 된다. 맨 앞에서는 0부터 시작해서 증가시켜 주고, 맨 뒤에서는 체인이 합쳐지므로, n-1부터 감소시키면 된다. 만약 두 값이 같아지면 반복을 종료하면 되는 것이다.

나는 합쳐진 체인에서 어떻게 고리를 빼다 쓰는 경우가 있지 않을까? 라고 생각해서 합한 값을 넣어줬는데 그럴 경우가 없다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    int answer = 0;
    int start = 0, end = n-1;
    // 체인이 두개가 될 때 까지, 가장 짧은 체인의 고리를 빼서 가장 긴 두 체인을 합친다.
    while(start<end) {
        v[start]--;
        if(v[start] == 0) start++;
        end--;
        answer++;
    }
    cout << answer;

    return 0;
}

코드가 한결 간결해 졌다.

더 빠르게 하고 싶다면, start가 1씩 감소하는데 이 값을 뭉탱이로 처리할 수도 있을것같다. 1 1 1 1 1 1 이런거만 아니면 좀 빨라질 것 같다.