백준 2437 자바 - 저울 (BOJ 2437 JAVA)

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

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2437.java

 

  일단 brute force(완전탐색)으로는 단순히 생각해봐도 2^1000 이므로 절대 무리다. 처음엔 DP류 일 것 같았는데, 결론적으로 완전 아이디어 하나로 풀리는 문제였다. 내 경우엔 공책에 막 여러 케이스 무지성으로 써보면서 확인해보다가 얻어걸렸다.

 

일단 '양의 정수 무게 중 최솟값' 이라는 부분에서, 최소값을 찾자마자 출력해야 할꺼라 판단하여 정렬부터 하고 생각했다. 그리고 잘 보면

애초에 '2 3 4 5 6' 이렇게 있어도 1이 없으면 1은 못만든다.

그다음으로 '1 3 4 5 6' 이런식으로 있어도 2는 만들 수 없다.

그 다음으로 못만드게 만드는 작은 수도 찾아봤다. '1 2 4 5 6' 과 같이 3은 없어도 만들 수 있다. 하지만 '1 2 5 6'과 같은 경우 4를 못만든다. 이쯤에서 정렬 후 작은 수부터 봤을 때 그 전까지의 합보다 2이상 차이나는 큰 수가 나오면 못만든다는 가설을 세웠다.

그리고 '1 1 1 5' 처럼 해보니 역시 4를 못만든다! 더 확인해보긴 뭐해서 일단 코드 짜서 넣어보니 맞았다. 완전 얻어걸림 ㅋㅋ

 

결론은, 정렬 후 작은 수 부터 확인할 때, i번째 수가 i-1까지의 합보다 2이상 크다면 'i-1까지의 합+1'이 답이다. 이러면 O(N)으로 끝나버린다. 이런 문제가 참 신기한 것 같다. 보통은 메모리를 희생하고 시간을 취하는 등 trade-off가 있기 마련인데, 하나의 아이디어만 넣었을 뿐인데 trade-off 무시하고 시간과 메모리 복잡도 둘다 더 좋아졌다. 원래라면 O(2^N)으로 계산해야 했을 문제를 O(N)으로 해결하게 되는데다, 심지어 메모리 복잡도도 N개 입력받은것만 유지하면 되니 O(N)으로 엄청 낮다. 이 맛에 PS 못끊지