[cpp 알고리즘] 백준 25943 양팔저울

[백준] 25943 양팔저울 cpp 풀이

2022 ICPC KOREA 인터넷 예선(Internet Competition) A번

구현, 그리디 알고리즘

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

문제 요약

- n개의 자갈이 순서대로 주어지고, 아래 두 가지 규칙을 고려하여 양팔저울에 올리면 된다.

   (1) 평형인 경우, 자갈을 양팔저울의 왼쪽에 올려둔다.

   (2) 평형이 아닌 경우, 양팔저울의 가벼운 쪽에 저울을 올려둔다.

- 최종적으로 양팔 저울의 평형을 맞추면 된다. 이 때는 1g, 2g, 5g, 10g, 20g, 50g, 100g의 7종류의 무게추를 사용하는데, 이 때 무게추의 최소 개수를 구하면 된다. 

풀이 정리

1. 자갈 N개의 개수만큼 반복문을 돌면서, 좌/우 중에 어디 두어야 하는지 코드를 작성한다. 이 때는 If 문을 이용해 평형인 경우와 아닌 경우로 나눠 코드를 구현했다.

2. 왼쪽, 오른쪽의 무게 차이를 구한 후에 무거운 추부터 사용해서 나눠준다. 몫 만큼의 무게 추 개수가 필요하고, 나머지 만큼의 무게는 더 나누어주어야 하는 무게이다. 

C++ 코드

#include <iostream>
using namespace std;

int main(){
    int N; //10000
    int arr[10001];
    
    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];
    
    int idx=0;
    int lsum=0; int rsum=0;
    while(idx<N){ //cnt=N인 순간에 종료
        if(lsum <= rsum) lsum += arr[idx];
        else rsum += arr[idx];
        idx++;
    }
    
    int diff = -1;
    if(lsum == rsum){
        cout << 0 << "\n";
        return 0;
    }
    else if(lsum > rsum){
        diff = lsum - rsum;
    }
    else{
        diff = rsum - lsum;
    }
    
    int ans = 0;
    if(diff>0){
        if(diff/100>0){
            ans += (diff/100);
            diff = diff%100;
            if(diff==0) {
                cout << ans << "\n";
                return 0;
            }
        }
        if(diff/50>0){
            ans += (diff/50);
            diff = diff%50;
            if(diff==0) {
                cout << ans << "\n";
                return 0;
            }
        }
        if(diff/20>0){
            ans += (diff/20);
            diff = diff%20;
            if(diff==0) {
                cout << ans << "\n";
                return 0;
            }
        }
        if(diff/10>0){
            ans += (diff/10);
            diff = diff%10;
            if(diff==0) {
                cout << ans << "\n";
                return 0;
            }
        }
        if(diff/5>0){
            ans += (diff/5);
            diff = diff%5;
            if(diff==0) {
                cout << ans << "\n";
                return 0;
            }
        }
        if(diff/2>0){
            ans += (diff/2);
            diff = diff%2;
            if(diff==0) {
                cout << ans << "\n";
                return 0;
            }
        }
        if(diff == 1){
            ans += 1;
            cout << ans << "\n";
        }
        else{ //diff=0;
            cout << ans << "\n";
        }
    }
    return 0;
}

 

기타

나는 If 문으로 나눴지만, 배열에 무게 추가 큰 순서대로 넣고, 0번 Index부터 반복문을 돌면서 검사하는 방법도 있다.

문제 풀면서 작성했던 노트