주어진 숫자로 만들 수 없는 최소 금액을 찾는 문제이다.

접근

처음 접근은 반복문을 돌면서 모든 경우의 수를 찾아서 리스트에 저장하고 1부터 확인해서 경우의 수에 없는 최소 숫자를 찾는 방법으로 해야겠다고 생각했으나 생각보다 너무 코드가 복잡해지고 문제가 의도한 방법이 아니라는 것을 깨달았고 여러번 시도하다가 결국 답지를 보게되었다.

해설

답지를 보아도 이해가 되지 않았다.정렬을 하는 것 까지는 알겠는데 Target 은 무엇이고 왜 이걸 더하는지..
그러다가 여러번 보니까 어느정도 이해는 되었다. 일단 이해가 안되어도 여러가지 경우를 해보자 그러면 어느정도 이해가 된다.
예를 들어서 [1, 2, 4] 의 숫자들이 있다고 해보자. 우리가 만들 수 있는지 확인할 숫자는 1 부터이다. 앞으로 우리가 확인할 숫자를 A 라고 해보자. 그리고 동전을 B 라고 하자.

A(확인할 숫자) : 1
B(동전) : 1

그러면 우리는 1을 만들 수 있다. 그리고 우리가 다음으로 만들 수 있는지 확인해볼 숫자는 1 + 1 해서 2이다. 이부분에서 왜 더하는지 이해가 안될 것이다. 그런데 일단 계속 해보자 보다보면 이해가 될 것이다.
동전은 다음 동전을 가지고 와서 2가 올 것이다.

A(확인할 숫자) : 2
B(동전) : 2

동전이 2이니까 2는 물론 만들 수 있다. 그러고 우리가 확인해볼 숫자는 2 + 2 해서 4이다. 여기서 왜 3은 확인 안해도 만들 수 있다고 확신하는지 이해가 안될 것이다. 그런데 직접 확인해보면 [1, 2] 가 있으면 3을 만들 수 있다는 것을 알 수 있다.

그럼 만약에 가지고 있는 동전이 [1, 2, 4] 가 아니라 [1, 1, 4] 라고 생각해보자. 처음 1은 만들 수 있으니까 생략하고

A(확인할 숫자) : 2
B(동전) : 1

다음 확인해볼 숫자는 2 + 1 해서 3이다. 다음 확인해볼 숫자는 3이다.
그런데 다음 동전은 4이여서 3을 만들 수 없다는 것을 알 수 있다.

즉, 확인할 숫자 + 동전 숫자 보다 작은 숫자들은 모두 만들 수 있다.
이해가 아직 잘 안될 수 있다. 그렇다면 더 확인해보자. 다시 동전이 [1, 2, 4] 가 있다고 해보고 2 + 2 해서 다음으로 만들 수 있는지 확인해볼 금액은 4이다. 그리고 다음 동전도 4이다.

A(확인할 숫자) : 4
B(동전) : 4

그러면 다음으로 올 수 있는지 확인해볼 금액은 8이다. 엥?? 그러면 7까지는 다 만들 수 있나? 확인해보면 다 만들 수 있다. 자세히 생각해보면 동전 4를 확인하기 전에 이미 1부터 3까지는 만들 수 있는 상태였다. 즉, [1, 2] 까지만 있을 때 1, 2, 3 까지는 만들 수 있었다. 거기에 추가로 4가 왔을 때면 당연히 4 + 1, 4 + 2, 4 + 3 까지해서 7까지는 만들 수 있다. 따라서 다음으로 만들 수 있는지 A(확인해볼 금액)는 8이다.

여기에 만약에 다음에 오는 동전이 6 이라고 해보자. [1, 2, 5] 로 만들 수 있는 숫자는 1, 2, 3, ... , 7 이였다 여기에 추가로 동전 6 이 있다면 당연히 6 + 1, 6 + 2,.. 6 + 7 까지 모든 경우가 만들어질 수 있으므로 최대 6 + 7 까지의 숫자는 만들 수 있는 것이다. 따라서 다음으로 확인해볼 금액은 6 + A(확인해볼 금액 : 8) 인 14이다.

그런데 여기에서 만약에 확인해볼 금액보다 숫자가 큰 동전이 온다면 어떨까? 지금까지 [1, 2, 5, 6] 으로 13까지는 만들 수 있는지 확인했고 A(확인해볼 금액) 는 14 이다. 여기에 만약에 15원 동전이 온다고 생각해보자.
지금까지 있는 동전으로 1, 2, ... 13까지는 만들 수 있었는데 여기에 15 동전이 추가된다면 15 + 1, 15 + 2 ... 15 + 13 까지해서 최대 28까지 만들 수 있지만 14는 만들 수 없다. 따라서 만들 수 없는 최소 금액은 14가 된다.

여기까지 하다보면 규칙을 발견할 수 있다.

만약에 A(확인해볼 숫자) >= B(확인하는 동전) 이면 A 는 A + B 로 업데이트 된다. 그런데 만약에 A < B 라면 만들 수 없는 최소 금액은 A 가 된다.

따라서 이를 코드로 만들면 다음과 같다.

n = int(input())
coins = list(map(int, input().split()))
coins.sort()
A = 1
for B in coins:
	if A < B:
		break
	A += B
print(A)
		

(물론 변수 명은 소문자로 하는게 좋은데 위에서 설명을 대문자로 하여서 이해하기 쉽게 변수 명을 A 와 B 로 바꾸었다. 해설지에 보면 Target 이라고 말하는 부분이 A 이다.)