Search

만들 수 없는 금액

문제 : 만들 수 없는 금액

2437번: 저울
문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/2437

풀이

해결에 필요한 핵심 아이디어: 현재 검사 요소가 그 전 요소까지의 합보다 크면 안된다!

해결 시나리오

•
주어진 리스트를 오름차순 정렬
•
순서대로 리스트 안 요소를 확인
◦
현재 요소가 target 보다 같거나 큰 경우에만 target에 현재 요소를 더해 갱신한다.
◦
그 외의 경우엔 break
•
최종 traget 값을 출력하면 만들 수 없는 값 중 최솟값이 나온다.
답안

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.

Made with