[BOJ 19590] 비드맨

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

19590번: 비드맨

 

- 문제 요약

 

비드맨은 서로 다른 종류의 구슬 두 개를 부딪히면 서로 깨져 없어진다는 것을 알고 있다.

이 사실을 이용해서 비드맨은 현재 가지고 있는 구슬의 개수를 최소로 하고자 한다.

서로 다른 종류의 구슬 두 개를 부딪혀서 최대한 구슬을 없앤다고 할 때 남게 되는 구슬의 개수는 몇 개인지 구하시오.

첫 번째 줄에는 비드맨이 가지고 있는 구슬의 종류 N이 주어진다.

두 번째 줄부터 N개의 줄에는 x1, x2​, x3, ..., xN이 주어진다. xi는 비드맨이 가지고 있는 i번째 종류의 구슬의 개수이다.

(1 ≤ N ≤ 10^5) / (1 ≤ xi ≤ 10^9)

 

 

- 알고리즘 정리

 

현재까지 중 가장 큰 값의 구슬을 mx, 나머지 구슬들의 총합을 sum이라고 하겠습니다.

이 문제에서 경우의 수는 두 가지로 나눠집니다.

1. mx > sum

2. mx <= sum

1번과 같은 경우에는 모든 구슬이 mx 구슬과 부딪히면 되므로 mx-sum을 출력해 주면 됩니다.

2번과 같은 경우에는 차례대로 구슬을 부딪히다 보면(문제에서 제공한 예제로 직접 시뮬레이션해보면 더 이해하기 편합니다) 남은 구슬의 개수가 0 또는 1이 되므로 이를 출력해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n,sum,mx;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		ll w;
		cin>>w;
		sum+=w;
		mx=max(mx,w);
	}
	sum-=mx;
	if(sum>=mx){
		if((sum+mx)%2==1){
			cout<<1;
		}
		else{
			cout<<0;
		}
	}
	else{
		cout<<mx-sum;
	}
}

코드 제출 결과