Search

[백준 2437] 저울

[백준 2437] 저울

Tip

정렬을 이용한 그리디 알고리즘으로 접근
측정할 수 있는 무게인지 1부터 차례대로 확인
추의 무게가 담긴 배열을 오름차순을 정렬
무게가 적은 추부터 차례대로 활용
EX
추의 무게 : 3, 1, 6, 2, 7, 30, 1
오름차순 정렬 : 1, 1, 2, 3, 6, 7, 30
차례대로 무게가 적은 추부터 확인하며 무게 측정 가능 여부 체크
확인하고자 하는 무게를 변수 target에 저장
초기 target : 1
추 무게 1 : 1
target : 2
추 무게 1 : 1, 2
target : 3
추 무게 2 : 1, 2, 3, 4
target : 5
추 무게 3 : 1, 2, 3, 4, 5, 6, 7
target : 8
추 무게 6 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
target : 14
추 무게 7 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
target : 21
추 무게 30 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 31....
무게 21 측정 불가능!
추 무게가 21 or 20 or 19 ... 인 경우엔 target : 21 가능
target < 현재 확인 중인 추 무게 인 경우 측정 불가능한 무게값이 나옴.

풀이 소스 코드

import sys si = sys.stdin.readline n = int(si()) array = list(map(int, si().split())) array.sort() # 추의 무게값들을 오름차순으로 정렬 # 추의 무게값들을 확인하면서 무게의 측정 가능 여부 체크 target = 1 # target의 초기값은 1로 for weight in array: # 측정 불가능한 target값일 땐 등장하면 그 즉시 반복문 탈출 if target < weight: break # 현재 확인하고 있는 추의 값을 기존 target에 더해줌으로써 다음 target값 설정 target += weight print(target)
Python