저울

송지용·2019년 5월 3일
0

algorithm

목록 보기
21/50

https://programmers.co.kr/learn/courses/30/lessons/42886

  • flow
    일단 추를 무게순으로 정렬하고, 특정 추의 무게가 n일 때, 그 추보다 작은 무게를 가진 추들 모두의 합이 n-1 보다 작으면 sum+1 ~ n-1 의 무게는 절대 잴 수 없다. 이 점을 이용하면 무게가 작은 추부터 차례대로 확인해 나아가면서 정답을 찾을 수 있다. 특정 시점에서 잴 수 있는 무게가 n까지라고 할 때, 다음 무게 m의 추가 n+1 보다 작거나 같다면 n+1 ~ n+m 까지 모두 잴 수 있는 논리가 성립되기 때문에 코드도 간단하게 나올 수 있다. O(N)은 덤

  • result
    https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A14.py

0개의 댓글