저울
-
백준 2437 저울Algorithm/BOJ 2020. 6. 13. 01:53
출처: www.acmicpc.net/problem/2437 분류: 그리디 접근방식 쉬워보였으나, 실제로도 방법만 알면 쉬우나, 쉽지 않았던 문제입니다 😭 추들이 주어질 때 측정할 수 없는 최소값을 구하는 문제입니다. 어떤 경우가 되면 더 이상 무게를 구할 수 없다고 판단할 수 있을까요? 추를 오름차순으로 정렬했을 때, 처음 추의 무게가 2라면, 절대 1은 만들 수가 없습니다. 1, 2 다음에 900이 나온다면? 최대로 3까지 만들 수가 있습니다. 1, 2, 3 다음에 900이 나온다면? 최대로 6까지 만들 수가 있습니다. 그렇다면 이제 다시 생각해볼까요? 저희는 직관적으로 알고 있습니다. 1, 2, 3 다음에 900이 나오면, 이미 900은 너무 큰 숫자니 제치고 그 전의 1, 2, 3가지고 최대를 찾아..