[C/C++ 백준 2785번] 체인 (Silver 2)

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

2785번: 체인

체인을 연결하는 방법 두가지를 조건에 따라 구현해주면 된다.

 

① 짧은 체인을 풀어 연결하는 경우

② 체인끼리 연결 부위를 연결하는 경우

 

인데, 짧은 체인을 풀어 연결하는 경우는 모두 쓸 수 있는것이 아니면 반드시 손해이므로, 모든 고리를 쓸 수 있을 때만 1번 방법을 쓰고, 나머지 경우는 2번을 쓴다. 참고로 풀어쓰는 고리는 가장 짧은 것을 고르나, 적당히 긴것을 골라 쓰나 열고 닫는 횟수는 같으므로 그냥 가장 짧은 것을 사용하자.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int n, chain[500001], mini=-1, ans=0, save;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d",&chain[i]);
	}
	sort(chain, chain+n);
	while(1){
		if(chain[0] <= n-2){
			save = chain[0];
			ans += chain[0];
			for(int j=n-1; j>=n-chain[0]; j--){
				chain[n-chain[0]-1] += chain[j];
			}
			for(int k=1; k<=n - chain[0] - 1; k++){
				chain[k-1]=chain[k];
			}	
			n = n - save -1;
		}
		else{
			ans += n-1;
			break;
		}	
	}
	printf("%d",ans);
}