백준 25943 양팔저울 / python

문제 : 25943

풀이 point

방법에 맞게 자갈을 왼쪽 저울, 오른쪽 저울에 올려준다.

왼쪽 저울과 오른쪽 저울의 차이를 구한다.

가장 최소 개수를 구하기 위해 100g부터 1g 추를 사용한다고 치고 100g 개수, 50g 개수 ... 1g 개수까지 구한다.

풀이 방법

그리디 문제이기 때문에 동전 거스름돈 문제처럼 가장 큰 무게 추 부터 사용한다고 치고 무게 추의 개수를 구해주면 된다. 그리디가 아니었다면 더 고민해봐야 할 문제지만 그리디 문제이기 때문에 쉽게 구할 수 있다.

코드

백준, 25943 양팔저울
N = int(input())

gravel = list(map(int, input().split()))
weight = [100, 50, 20, 10, 5, 2, 1]

left = gravel[0]; right = gravel[1]
for i in range(2, N):
    if left > right:
        right += gravel[i]
    else:
        left += gravel[i]

diff = abs(left - right)

cnt = 0
for i in weight:
    cnt += diff//i
    diff %= i

print(cnt)