[Algorithm] Baekjoon 2785번 : 체인

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

2785번: 체인

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, l;
    vector<int> v;
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> l;
 
        v.push_back(l);
    }
 
    sort(v.begin(), v.end());
    int elementCount = n;
    int count = 0;
    bool isBreak = false;
 
    for (int i = 0; i < v.size(); ++i)
    {
        int stand = v[i]; // 하나 집는다.
 
        while (1)
        {
            --stand;
            --elementCount;
            ++count;
 
            // 탈출조건은 다 연결해서 한덩어리가 되거나(elementCount == 1), stand가 0이되버리는것.
 
            if (stand == 0)
            {
                --elementCount; // 집은거 자체가 사라지기때문에 한번더 -1.
                break; // 0이 됐으니 다음꺼 뽑아야됨.
            }
 
            if (elementCount == 1) 
            {
                break;
            }
        }
 
        if (elementCount <= 1)
        {
            break;
        }
    }
     
    cout << count;
}

문제 예제테스트케이스 보더라도 바로 이해안되서 조금 헤맨 문제.

고리를 '몇번' '열고 닫아야'하는지 세야 하는 문제다. 열고 닫는게 한번의 카운트다.

 

먼저 오름차순 정렬을 한다.즉, 가장 길이가 짧은 체인을 먼저 집는다.

그리고 집은 체인에서 고리 1개를 열어서 뺀다. 그러면 1개의 열려있는 고리를 얻게 되는데, 이 고리로 두개의 체인을 연결할 수 있다. (연결 후 닫기) 즉, 두개의 체인을 한개의 체인으로 만들 수 있다는 의미이다.

이 작업을 최종적으로 한개의 체인이 될때까지 반복해준다.

만약 한개의 체인이 되기전에 '집은 체인'이 0개, 즉 고리를 다 빼서 써버린다면 다음 체인을 집으면 된다.

 

단, 집은 체인이 0이 된다면 그 체인자체가 아예 사라져버린것이기 때문에 전체 체인카운트에서 추가적으로 -1을 해줘야한다.

 

while문 밖의 if문에서 elementCount <= 1인 이유는(while문 안과 달리), 집은 체인의 고리수가 0이되어 while문을 빠져나온 경우에는 추가적으로 -1을 했기 때문에 0이 되는 경우의 수가 존재하기 때문이다.