[python]이코테 - 만들 수 없는 금액(그리디)

쉬워보이는데 안풀려서 화가났다.

 

알고리즘을 계속 공부하는데 왜이렇게 머리가 안굴러가는거지?

시간만 낭비하는것같고 실력은 오르지않는것같다.

내가 코딩을 할 머리가 아닌가? 바보 멍청이다.

 

 

 

n = input()
arr = list(map(int, input().split()))

target = 1
arr.sort()
for i in arr :
    if target < i : 
        break
    else : target += i


print(target)

 

 

target은 내가 만들 수없는 수를 뜻한다. 

처음에 1부터 시작한다. 

 

입력받은 수를 정렬하여 오름차순으로 만든다.

 

동전 중 가장 작은 수가 내가 만들 수 없는 수보다 크다면 그게 답이다

 

만약 내가 만들 수 없는 수 보다 작다면 그 수를 더해서 만들 수 없는 수를 upgrade한다.

 

 

 

---

 

아니 이걸 어떻게 생각하냐구

진짜;;;

 

 

그래도 예를 들어보면 

1, 1, 1, 5 가 있을때

 

target은 1부터 시작해서 5를 고려할때까지 

1씩 증가하며 4가 되었다. 이는 임시적인 "내가 만들 수 없는 수"이다.

 

만약 여기서 다음 수 가 이것보다 크다면 확정이다. 

그 다음 수는 5이므로 4가 답이다.

 

그 이유는 만약 다음 수가 4일 경우엔 그 하나로 4(target)이 만족되기 때문에 가능하고

4보다 작은 숫자라면 

4까지 순서대로 잘 만들어왔기에 1, 2, 3 도 잘 있을것이므로 4 + 4가 다음 임시적인 " 내가 만들 수 없는 수"이다. 

 

 

누적합+1 보다 화폐단위가 크면 그 사이 만들 수 없는 수가 있는것이다. 

 

 

근데 이거를 어떻게 그냥 생각하지 ?

내가 너무 부족한것같아 나에게 실망했고 화가난다.