25943: 양팔저울

• toc {:toc}

문제 확인하기

풀이

풀이는 좌측, 우측 규칙대로 자갈을 올려놓는다. 이후, 두 무게의 차이를 빼서 주어진 무게추를 무거운 순서부터 양팔의 무게 차이보다 무게추의 무게가 작다면 무게추를 올려두는 방식대로 풀이했다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
int weight[8] = {100, 50, 20, 10, 5, 2, 1};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, left = 0, right = 0;
    int res = 0;
 
    cin >> n;
 
    for(int i = 0; i < n; i++){
        if(i == 0) cin >> left;
        else if(i == 1) cin >> right;
        else{
            int val;
            cin >> val;
            if(left > right) right += val;
            else left += val;
        }
    }
    int diff = abs(left - right);
 
    for(int i = 0; i < 7; i++){
        if(weight[i] <= diff){
            res += diff / weight[i];
            diff = diff % weight[i];
        }
    }
    cout << res << endl;
 
    return 0;
}

풀고나서 생각해보다 보니 왼쪽에 5, 오른쪽에 14가 주어진 경우 내 코드는 왼쪽에 5g, 2g, 2g 무게추를 사용하여 3개가 되는데, 왼쪽에 10g을 추가하고 오른쪽에 1g을 추가하면 2개만 사용해서 풀 수 있기에 최소 개수가 2가 되어야 문제에 올바른 코드 아닌가? 혼동을 막으려면 가벼운 쪽에’만’ 과 같은 제한이 필요하지 않을까 싶다.