문제
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
bool cmp(ll a, ll b){
return a> b;
}
int main(){
ll sum = 0;
ll m; ll c;
vector<ll> v;
cin >> n;
for(int i = 0; i < n; i++){
cin >> c;
v.push_back(c);
}
sort(v.begin(), v.end(), cmp);
m = v[0];
for(int i = 1; i < v.size(); i++){
sum += v[i];
}
if(m >= sum) cout << m - sum << '\n';
else{
if(m % 2 == sum % 2) cout << 0 << '\n';
else cout << 1 << '\n';
}
return 0;
}풀이
1번째 떠올린 방법은 정렬이었다.
내림차순 정렬 후 1번째 idx에 있는 배열 값으로 0번째 idx에 있는 배열 값을 빼주고 다시 정렬 하려고 했으나 입력 최대 값이 10만이라 시간이 너무 오래 걸릴듯 했다.
2번째 떠올린 방법은 자료구조를 사용하는 것이었다.
정렬하고 stack에 가장 큰 값을 push 한다. 이 후 값부터 stack.top에 들어있는 값과 비교해서 top이 더 크면 top - 다음idx 값 or 다음 idx - top 값으로 넣고 빼고 해서 마지막에 top에 있는 값을 출력하려고 했으나 코드가 실행이 안됐다.
--> 아직 이유는 찾지 못했다. 느낌 상 stack이 비는 타이밍이 생겨 그 때 오류가 생기는 것 같은데 좀 더 찾아봐야 할 듯 하다.
stack으로 안되는 부분을 queue로 시도했다.
내림차순 정렬 후 값을 넣고 빼고를 반복했는데 오답이었다.
서로 다른 2개의 구슬이 만나면 깨진다. 3개가 들어오고 4, 8, 8 이면 기존의 생각은 4가 남아야했다면 틀린 생각이었다.
8개에서 2개, 4개 중에 2개를 미리 깨뜨리고 남은 6개씩 깨뜨리면 되는 것이다.
기존의 생각을 바꿔 생각했다.
가장 큰 값을 m이라 할 때 m보다 나머지 입력 값의 합(sum)이 더 작거나 같으면 그냥 m - sum을 출력하면 된다.
그런데 m < sum인 경우는 하나씩 해보면 m을 나눈 나머지와 sum을 나눈 나머지가 같냐 다르냐의 따라 값이 결정됐다.
결과
후기
특별한 알고리즘, 스킬 필요없이 그리디함을 요구하는 문제였다.
생각보다 쉬운데 생각보다 어려웠다.
생각의 반례가 존재함을 인정하는 것도 쉽지 않았고 생각을 아예 뜯어 고치는 것은 더욱 쉽지 않았다.
