[99클럽 코테 스터디 9일차 TIL 그리디] 백준 2437 저울 Python

오늘의 학습 키워드

그리디

공부한 내용 본인의 언어로 정리하기

문제

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

코드

n = int(input())
weight = list(map(int, input().split()))
weight.sort()
count = 1
for w in weight:
    if w > count:
        break
    count += w

print(count)

 

 

해당 문제는 현재 좋은 것만 생각하는, 즉 그리디 문제이다. 따라서 먼저 무게를 받고, 해당 무게를 오름차순으로 정리한다. 이후 count를 점점 늘려가며 계산 불가능한 최소 값을 구해준다. count는 현재 가진 추로 만들 수 있는 수의 범위를 말한다. count의 초기 값은 1로 둔다.(가장 작은 자연수)

이후 weight에 있는 추의 무게를 순회하며 count와 비교한다. 만일 weight가 현재 count보다 작거나 같다면, 즉 현재 만들 수 있는 수의 값의 범위가 w보다 작거나 같다면, 현재 추를 count에 추가하여 추로 만들 수 있는 무게의 범위를 넓힐 수 있다. 하지만 추의 무게가 현재 count보다 크다면, 현재 count가 더 이상 만들 수 없는 최소의 무게가 된다. 

 

오늘의 회고

골드 2라고 해서 겁먹었는데 생각보다 코드가 많이 짧았다. 그대신 알고리즘을 생각해내는게 어려워서 애를 먹었던 것 같다. 그리디 알고리즘은 가장 좋아 보이는 선택을 하는 알고리즘으로, 전체 문제에서 최적의 해를 보장한다. 당장 다음 것만 보고 결정하는 그리디 알고리즘에 대해 배울 수 있는 시간이었다.