백준 2437번 - 저울 (JAVA)

문제링크

 

 

문제 풀이 방법

처음에 이 문제를 접했을 때는 이진 탐색으로 해결하려고 했다가 코드가 더 복잡해지고 시간 초과 될 것 같아서 다른 방법을 찾아야했다.

규칙을 찾으면 생각보다 쉽게 해결 되는 문제이다.

 

문제에 있는 예제로 설명을 하면, 우선 주어진 추들을 정렬을 해야한다.

 

 

1번추로 측정 할 수 있는 무게는 1이다.

 

2번째 추까지 이용하여 측정 가능한 무게는 2이다.

 

2번째까지 측정 가능한 무게는 2이며, + 1을 하면 3이다. 3은 3번째 추(2)보다 크므로 3은 측정이 가능하며, 3번째까지 측정 가능한 무게는 4가 된다.

 

4번째 추를 이용하여 측정 가능한 무게는 7이다.

 

5번째 추를 이용하여 측정 가능한 무게는 13이다.

 

 

6번째 추를 이용하여 측정 가능한 무게는 20이다.

여기서 20 + 1을 하면 21인데 다음 추가 30이므로 21은 측정이 불가하다.

 

 

즉 현재 추를 이용하여 측정이 가능한 최대 무게에서 + 1 한 숫자와 다음 추의 무게를 비교했을때 다음 추의 무게가 더 크면 측정이 불가능한 무게가 된다.

 

전체 코드