[C++] 백준 | 19590번 비드맨

19590번: 비드맨

재밌는 그리디 문제이다.

 

종류가 다른 구슬을 2개씩 부딪혀 깰 수 있다고 할 때, 

최소한의 구슬을 남기는 문제다.

 

25635번: 자유 이용권

비슷한 문제로 자유 이용권 문제가 있다.

 

풀이 방법은,

가장 많은 개수의 구슬을 n, 나머지 총합을 m으로 뒀을 때

1. n > m 이라면 무조건 n - m 의 구슬은 남고, 나머지는 깰 수 있다.

2. n = m 이라면 0개의 구슬만 남는다.

3. n < m 이라면 전체 구슬이 홀수라면 1개가, 아니라면 0개가 남는다.

 

따라서 아래와 같이 작성할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;
long long n, m,k,arr[100001];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>k;
    
    for(int i = 0; i < k; i++) cin>>arr[i];
    sort(arr, arr + k);
    
    n = arr[k - 1]; //최댓값
    for(int i = 0; i < k - 1; i++) {
        m += arr[i]; //나머지
    }
    if(n > m) cout<< n - m;
    else {
        if((n + m) % 2) cout<<1;
        else cout<<0;
    }
}

추가적으로

27311번: 치노의 라떼 아트 (Easy)

이 문제를 풀지 못해서 너무 스트레스 받는다..

실버 2의 마인크래프트를 어떻게 푸는지 모를 때의 기분과 같다.