백준 2437. 저울

https://www.acmicpc.net/problem/2437

2437번: 저울

 

이런 문제가 정말 어려운 문제인것 같다.

푸는 방법이 바로 떠오르면 정말 쉽게 풀리지만 떠오르지 않으면 정말 어려워진다.

그리디, dp 류의 문제들이 그런것 같다.

 

우리가 구하는건 추들을 사용해 측정할수 없는 최소 무게이다.

따라서 우선 주어진 추들을 오름차순하고 작은 추부터 올려보면서 측정 불가능한 무게를 찾아야한다.

결론부터 말하면 다음에 올릴 저울추가 현재 까지 올린 저울의 누적합 + 1 보다 커지면, 누적합 + 1이 답이다.

 

왜 이렇게 되는지를 생각해보면, 우선 중요한것이 우리가 구하는게 측정 불가능한 최소 무게라는 것이다. 

즉 만약에 1짜리 저울추가 주어지지 않으면 답은 1일 것이다. 

우리는 무게를 1씩 늘리면서 탐색하기 때문에 누적합 S까지 구했다는 것은 무게 S까지는 만들수 있다는 것이다. 

그런데 다음에 올릴 추가 현재까지 구한 누적합 S+1 보다 커지면, S+1을 구할 방법이 없어진다.

 

 

예를들어 주어진 무게추가 다음과 같다

1 1 2 3 6 7 30

여섯번째 추인 7까지 구했다고 치면 누적합 S = 20 이다. 

따라서 무게 20까지는 우리는 만들수 있다.

다음 추를 보니까 30이다.

이러면 현재까지 구한 누적합 S에 1을 더한 21을 구할수가 없다.

 

만약 다음추가 30이 아닌 10이었다고 생각해보자.

1 1 2 3 6 7 10

마찬가지로 여섯번째 추인 7까지 구했고 누적합은 S = 20이다.

다음 추까지 더하면 누적합은 S = 30이된다.

그럼 21은? 당연히 만들수 있다.

왜냐하면 우리는 무게 1부터 쌓아올렸기 때문에 1~S까지의 모든 무게를 만들수 있다.

따라서 현재까지 구한 무게 30, 그리고 당연히 그 안에 9도 포함되어 있기 때문에 30-9=21이 된다.