[이것이 코딩 테스트다] 만들 수 없는 금액 - Python

<풀이>

개인적으로 지금의 나에게 좀 어려웠다. (어려웠다기보다는 어떻게 풀어야 하는지를 모르곘다는게 맞는거일수도..) 이문제를 어려워하면 아직 그리디 문제를 많이 접하지 않는거라고 하는데.. 그런거 같다.

이 문제는 target을 1로 두고 target이 입력값을 정렬했을때 첫번째 부터 시작해서 모든 값들과 비교를 한다 만약 target값이 작으면 바로 반복문을 끝낸 후에 target을 출력하면 된다. 만약 target이 크다면 해당 값에 비교한 리스트의 값을 더해준다.

(target은 해당 값 -1까지 만들 수 있다는 말이다)

 

1,2,3 입력값이 주어졌을때 

1

2

3

4 ( 1 + 3)

5 ( 2 + 3)

6 ( 1 + 2 + 3)

까지 만들 수 있다. 이때 target 값은 처음은 항상 1이고 이후 1+1 =2, 2+2 = 4, 4 +3 = 7 해서 6까지 만들 수 있다는것을 알 수 있다(target-1까지 만들 수 있으므로)

만약 위 리스트 에 5까지 있다고 가정하면 다음 target이 5보다 크니까 다음 target은 7 + 5 = 12 즉 11까지 만들 수 있다.

(실제로 해봐도 11까지 값이 만들어지는 것을 확인할 수 있다.)

그런데 만약 5가아닌 8이 있다고 가정했을때는 어떻게 될까?

target값은 7인데 다음 값은 8이므로 target값은 7이므로 종료가 된다(실제로해보면 7은 만들 수 없는 것을 확인할 수 있다.)

 

<코드>

n = int(input())
data = list(map(int,input().split()))
data.sort()

target = 1
for x in data:
    if target < x:
        break
    target += x
print(target)