개인적으로 그리디 알고리즘 중 가장 아이디어를 떠올리기 어려웠다.
각각의 추를 더하고 빼고 난리법석을 피웠는데도 이거다! 싶은 아이디어가 나오질 않았다.
그리디 알고리즘은 이거다!하는 느낌이 아니면 웬만하면 답이 아니더라...😢
해답
n = int(input())
list = list(map(int, input().split()))
list.sort()
target = 1
for i in list:
if i > target:
break
target += i
print(target)코드만 보면 정말 간단하다. 아이디어가 중요한 그리디 문제의 경우는 보통 코드가 자질구레해지지 않는 것 같다.
핵심 아이디어는 숫자를 오름차순으로 정렬하는 것과 그 숫자의 합보다 다음 숫자가 크면 그 숫자의 + 1이 측정할 수 없는 양의 정수의 최솟값이라는 것이다.
처음에는 이해하기 어려웠으나 나름대로 해석하면 다음과 같다.
-
target은 숫자의 합이다. 어차피 마지막에 찾은 숫자에 +1을 해줘야하므로 처음부터 1로 가지고 간다. 이는 마지막 단계에서 설명하겠다.
-
추의 무게가 [3, 1, 6, 2, 7, 30, 1]로 들어온다면 오름차순으로 정렬하여 [1, 1, 2, 3, 6, 7, 30]로 만든다.
-
추 리스트를 반복문으로 한 바퀴 돌린다.
-
처음에 1이 들어오면, 측정할 수 있는 무게는 현재 1이다. 다음 1이 들어오면 측정할 수 있는 무게는 1과 2(1+1)가 되며 추의 총합은 2이다.
-
그 다음은 2가 들어올 것이며 측정할 수 있는 무게는 1, 2(1+1), 3(1+2), 4(1+1+2)가 되며 추의 총합은 4가 된다.
-
그 다음은 3이 들어올 것이며 측정할 수 있는 무게는 1, 2(1+1), 3(1+2), 4(1+1+2), 5(1+1+3), 6(1+2+3), 7(1+1+2+3)가 되며, 추의 총합은 7이 된다.
-
그 다음은 6이 들어올 것이며 측정할 수 있는 무게는 1, 2(1+1), 3(1+2), 4(1+1+2), 5(1+1+3), 6(1+2+3), 7(1+1+2+3), 8(1+1+6), 9(1+2+6), 10(1+1+2+6), 11(1+1+3+6), 12(1+2+3+6), 13(1+1+2+3+6)가 되며 추의 총합은 13이 된다.
-
지금까지 반복문을 돌면서 혹시 캐치한 것이 있나?
바로 현재 측정할 수 있는 무게에 새로운 추의 무게를 더하면 처음부터 새로운 추를 더한 총합까지 측정할 수 있다는 것이다. -
7까지 추가되었다고 치고 30이 들어오는 것을 보자. 앞에서 본대로 7 까지 더한 추의 총합은 20이 될 것이다.
즉, 측정할 수 있는 무게가 현재 20이라는 뜻이다. 30이 추가되면 다음 측정할 수 있는 무게는 어떻게 될까?
현재 측정할 수 있는 무게(1~20)에 30을 모두 더해보자. 31 ~ 51이 된다. 따라서 21 ~ 30 구간은 측정할 수가 없다. -
정답은 도출됐다. 다음에 들어올 추의 무게가 현재 추의 총합보다 크면 안된다. 따라서 21보다 작은 수가 들어와야 21을 측정할 수가 있는 것이다.
측정할 수 없는 최솟값을 출력해야하기 때문에 현재 추의 총합 + 1(다음 숫자)가 정답이다. 하지만 우리는 target을 애초에 1을 할당해주었으므로 + 1은 생략이 가능하다.
반복문을 돌리다보니 단계가 길어졌다. 그 만큼 한 번에 이해하기 어려운 아이디어였다.
실패 후 성장
글의 초반에서도 말했지만 그리디 알고리즘은 아이디어가 핵심인 것 같다. 아이디어를 캐치하면 간단한 로직으로도 풀이를 할 수 있는 알고리즘이다. 코드가 자질구레해진다면 과감하게 버리고 다시 생각할 필요가 있다. 명심하자.
