문제 링크 : https://www.acmicpc.net/problem/2437
구현은 쉽지만, 아이디어 자체를 떠올리기가 쉽지 않은 문제였다.
오랫동안 고민하다가 도저히 모르겠어서 구글링해서 다른 분들의 코드를 읽고 이해했다,,
가지고 있는 무게 추를 가지고 만들 수 있는 총 무게를 어떻게 만드느냐가 관건인 것 같아서 처음엔 combintation을 떠올렸지만, 1<=N<=1,000 이기 때문에 시간복잡도 테스트에서 걸리게 된다.
"그리디"알고리즘 이기 때문에, 케이스를 전부 구하는 문제는 아니다.
그리디는 현재의 상황에서 가장 최적의 해를 구해나가는 탐욕적 알고리즘이다..
이 문제는 "이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오." 이기 때문에 그때 그때 측정할 수 있는 무게들을 생각하고, 그 다음 step에 경우의 수를 얹어나가면 된다.
핵심 아이디어는 다음과 같다.
- 먼저 추의 무게를 오름차순으로 정렬한다.
- 현재까지 측정가능한 최대 무게 (M) 가 무엇인지 구한다.
- 만약 다음 step에 추가할 추의 무게가 (M+1)보다 크다면, (M+1)이 정답이다.
왜 ? ? ... 진짜 이거 다른 분들 정답코드 읽었는데도 이해하기 힘들었다. 하.
예를 들어, 추의 무게 리스트 chu = [1, 1, 2, 3, 6, 7, 30] 일 때를 가정한다.
현재까지 측정 가능한 최대 무게 (M=0)로 세팅하고 시작한다.
왜냐하면 chu[0] 값이 M+1 = 1 보다 크다면 그냥 1이 답이기 때문이다.
본격적으로 chu 리스트를 차근차근 살펴본다..
-
chu[0] = 1
추 리스트에서 1kg를 획득한다. 측정 가능한 최대 무게(M) 은 1이다. -
chu[1] = 1
추 리스트에서 1kg를 하나 더 획득한다. M = 2가된다. -
chu[2] = 2
추 리스트에서 2kg을 획득한다.
여태까지 측정 가능한 무게 M = 2였기 때문에,
1,2를 측정 할 수 있었다는 뜻이고,
이 무게들을 지금 추가할 2kg에 더하면 2+1 = 3, 2+2 = 4.
최대 4 까지 모두 확실하게 측정할 수 있게된다.
따라서 M = 4 -
chu[3] = 3
같은 논리로, 여태 측정 가능한 무게들은 1,2,3,4 였다.
여기에 3이 추가되면,
3+1, 3+2, 3+3, 3+4 들이 새롭게 측정 가능하게 되는 것이다.
따라서 M = 7 -
chu[4] = 6
마찬가지로 M = 7 + 6 = 13 까지 모두 측정할 수 있다. -
chu[5] = 7
M = 13 + 7 = 21 까지 모두 측정할 수 있다. -
chu[6] = 30
여기가 중요하다..
현재까지 측정 가능한 스펙트럼은 (1~21)kg 이다.
그런데 여기서 30kg 짜리 추를 추가하려고 한다.
그럼 새롭게 측정 가능해지는 범위는,
(1~21)kg, (30~51)kg 이 되는 것이다.
따라서 측정 불가능한 무게의 최댓값은 그 전 M 값에 1을 더한 22kg 이다.
이런 논리로 알고리즘을 작성하면 O(N) time에 문제를 해결하게된다.
정답 코드
import sys
N = int(input())
chu = list(map(int, sys.stdin.readline().split()))
chu.sort()
M = 0
for c in chu:
if M+1 < c:
break
else:
M += c
print(M+1)