[BOJ] 2785번: 체인

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

2785번: 체인

---

접근 방법

처음에는 체인의 길이가 1인 것이 특별하다고 생각해서 주어진 체인의 길이가 1인 것을 먼저 사용해서 3세트 -> 1세트로 만들어주고, 남은 것들은 2세트 -> 1세트로 묶어주는 연산을 하는 것이 "고리를 최소로 사용한다"라고 착각했다.

위와 같이 생각하면, 예제 입력3을 통과하지 하게 되어서 다시 생각하게 되었다.

 

체인의 길이가 1인 것이 특별한 것은 아직 유효한데, 이 점을 극한으로 사용해야 한다.

남은 세트가 3세트 이상이면, 무조건 주어진 체인의 길이가 1인 것을 사용할 수 있다.

체인의 길이가 가장 작은 곳에서 고리 1개씩 떼어서, 당시의 체인의 길이가 긴 것 2개를 이어준다는 식으로 풀이하면 고리를 최소한으로 사용할 수 있다.

 

사실 고리를 그 자리에서 열고 닫는 것이 최적일거라는 편견이 처음과 같은 생각을 이끌어 낸 것 같다.

구해야 하는 것은 "고리의 최소 사용 횟수"이므로, 위와 같은 편견을 깨야 한다.

 

만약 예제 입력3이 없었다면 푸는데 더 오래 걸렸을 것 같다.

---

풀이

mxindex = 현재 가장 길게 묶인 체인의 인덱스

use = 현재 고리 1개씩을 떼어 내는 체인의 인덱스

라 생각하고, use\(<\)mxindex 일때까지 고리 1개를 떼어내서 이어주는 것을 반복해주면 된다.

 use \(=\) mxindex 인 경우는 떼어내는 체인의 인덱스가 현재 가장 길게 묶인 체인의 인덱스에 포함하므로, 연산을 하면 안된다.

---

시간 복잡도

n개의 각각의 체인 길이를 정렬해야 하므로 \( O(nlgn) \) 이다.

---

코드

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
void solve()
{
    ll n; cin>>n;
    ll l[n], ans=0, mxindex=n-1, use=0;
    for(int i=0;i<n;i++) cin>>l[i];
    sort(l, l+n);
    while(mxindex>use)
    {
        l[use]--;
        if(l[use]==0) use++;
        mxindex-=1;
        ans++;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1;
    while(tc--) solve();
    return 0;
}