Baekjoon 19590번 비드맨

문제

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

걸린 시간

- 실패

풀이

C++

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    long long total = 0;
    int tmp, m = 0; // m : 최대값
    for(int i = 0; i < n; i++){
        cin >> tmp;
        total += tmp;
        m = max(m, tmp);
    }
    if((total-m) > m)
        cout << (total&1) << "\n";
    else
        cout << m-(total-m) << "\n";

    return 0;
}

다른 사람의 풀이를 보기 전까지는 구슬의 개수가 제일 작은 종류를 제일 큰 종류와 부딪혀 없애가는 탐욕스런 방법으로 풀이하려 했다.

이는 구현도 복잡할 뿐더러 최대 입력이 구슬의 종류가 10만개, 개수가 10억개이기 때문에 일일이 구슬을 서로 부딪혀 2개씩 없애가는건 너무나 오랜 시간이 걸린다

문제의 해결책은 구슬의 총합과 최대값을 이용한 간단한 규칙에 있었다.

1000000000
// 답 : 1000000000

50 100
// 답 : 50

2 2 4
// 답 : 0

2 7 7
// 답 : 0

2 6 7
// 답 : 1

1 2 3 4 5
// 답 : 1

위의 테스트 케이스들을 잘 살펴보면 0, 1, 1보다 큰 값 으로 나뉘게 된다. 여기서 구슬의 총합과 최대값을 각각 계산해보면 총합-최대값 이 최대값 보다 작거나 같은 경우는 1보다 큰 값이 나오고, 큰 경우는 0또는 1값이 나온다는 걸 알아낼 수 있다.

1보다 큰 값은 최대값에서 최대값을 제외한 나머지 값들을 뺀 값, 0또는 1은 각각 짝수일 경우 홀수일 경우로 나뉘므로 총합에 &(and) 연산을 하여 출력하면 된다.

손으로 더 많은 예제를 직접 풀어봤으면 규칙을 발견할 수도 있었던 문제. 풀이과정에서만이 아닌 출력 값에도 규칙이 존재할 수 있다는 걸 꼭 기억하자.

참고

• 백준 19590 비드맨 - Yoonseop's Corgaxm