Q4. 만들 수 없는 금액

동전의 개수 N과 각 동전이 몇 원인지 숫자 N개가 주어진다.

동전들을 조합하여 만들 수 없는 금액 중 최소값을 구하시오

ex)

입력

5

3 2 1 1 9

출력

8

설명

3,2,1,1,9를 잘 조합해서 더하면 1부터 7까지는 만들 수 있는데 8은 만들 수 없다.

 

N은 최대 1000

동전들은 최대 100000원

 

idea

음.. 오름차순으로 정렬해보면 되지 않을까?

오름차순으로 정렬해서 맨 앞에서부터 하나하나 더하면서

1을 만들 수 있는지 2를 만들 수 있는지... 체크해보는건 어떨까

 

라고 생각을 해봤는데 이러면 안된다 ㅋㅋㅋㅋㅋ

위 예시에서 3은 1이랑 2를 조합해야되는데 이런 방법으로 하면 3을 못만듬. 1 -> 1 -> 2 이순서로 더하게돼서 ㅋㅋ ㅠ

 

흠 어떻게할까...

 

정답을 봤는데 이해가 안감

일단 정렬하는건 비슷한데..

 

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)

 

target을 정해서 1씩 증가시켜가며 확인하는것도 비슷.

근데 이게 왜.. 되는거지?

 

인풋이 3 2 1 1 9면..

첨에 target이 1

1 < 1은 성립하지 않으니

target += 1

target은 2가 된다.

2< 1은 성립하지 않으니

target += 1

target은 3이 된다.

3 < 2가 성립하지 않으니

target += 2

target은 5가 된다

5 < 3은 성립하지 않으니

target += 3

target은 8이 된다

8 < 9가 성립하니까

target = 8

 

어... 왜 되는거지?ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

도저히 이해가 안된다 ㅋㅋㅋㅋㅋ

 

-----------------------------추가-------------------------------

방금 다른 블로그 해설을 보고 조금 이해가 됐다.

[1 9] 의 예시를 보자.

[1]만 있을 때 만들 수 있는 숫자는? 1이 들어가는 경우 안들어가는 경우 다 고려하면 0~1까지의 범위의 숫자를 만들 수 있다.

여기에 9가 갑자기 들어오면?

9+0 ~ 9+1까지의 범위를 추가로 만들 수 있다.

즉 [1,9]로 만들 수 있는 숫자는

0~1, 9~10 해서 0,1,9,10이다.

기존 리스트로 만들 수 있는 숫자범위 0~1과 기존리스트+새숫자로 만들수있는 범위 9~10 사이에 텅빈공간 2~8이 생겼으니 정답은 그 최솟값인 2다.

 

[1 2 3]의 예시를 보자.

첫 번째 숫자만 고려할 때 만들 수 있는 숫자범위는 0~1

두 번째 숫자까지 고려하면 0~1과 2+0~2+1의 합집합. 즉 0~1과 2~3. 두 범위 사이에 빈공간이 없이 정수로서 쭉 이어지므로 [1 2]로는 0~3까지 만들 수 있다.

세 번째 숫자를 고려해보자. 기존 리스트로 만들 수 있는 숫자범위 0~3, 새 숫자+기존리스트범위 = 3+0~3+3인 3~6

0~3과 3~6은 쭉 이어지므로 0~6까지 만들 수 있게 된다.

 

자 그니까 숫자를 하나하나 받아서 더해가면서 새 숫자가 들어왔을 때 만들 수 있는 숫자 범위 중간에 빈공간이 생기나 안생기나 확인하면 되는 것이다. 어떻게 확인할까? 기존 리스트로 만들 수 있는 숫자 최대값 + 1 >= 새 숫자가 무조건 쓰일때의 최소값 이어야 된다.

다시 코드를 잘보자

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

 

target이 바로 [기존 리스트로 만들 수 있는 숫자 최대값 + 1]이다.

처음엔 아무 숫자도 고려하지 않으니까 1이상의 수를 못만들어서 target이 1로 시작한다.

새 숫자 x가 들어왔을 때, 새 숫자가 무조건 쓰인다고 가정하면 그 최소값은 새 숫자 그 자체가 된다.

if target < x 이 부분은

기존 리스트로 만들 수 없는 최소값 < 새 숫자가 쓰일 때의 최소값

을 비교하는 것이다.

예를 들어 [1 1]이 있다고 쳤을 때 기존 리스트로는 최대 2까지 만들 수 있고 만들 수 없는 숫자는 3이다.

새 숫자가 들어옴으로써 이 3을 만들 수 있게되면 반복문을 break할 필요가 없다. 근데 새 숫자가 4면은

기존 범위 0~2에 추가로 4~6까지 만들 수 있게 된다. 즉 3 < 4이므로 중간이 비게된다. 그럼 반복문은 break되고 정답은 3이 된다. 만약 새 숫자가 4가 아니라 3이면 기존범위 0~2에 추가로 3~5까지 만들 수 있게 된다. 그럼 기존범위로 만들 수 없는 최소값 3이 새 숫자가 쓰였을 때의 범위에서 최솟값 3으로 커버가 되므로 다음 target을 6으로 잡고 반복문을 계속하면 되는것이다.

 

아 최대한 설명을 풀어보려고했는데 미래의 내가 이문제를 까먹었을 때 이걸 다시 보고 이해할수있을지 걱정이된다..ㅋㅋㅋㅋㅋ