[이코테] 만들 수 없는 금액

가지고 있는 화폐를 작은단위부터 하나씩 꺼내보며, 만들 수 있는 금액을 체크해보면서 규칙을 찾으면 된다.

 

문제 예시를 통해 차근차근 생각해보자.

 

가지고 있는 화폐는 [1a, 1b, 2, 3, 9]이다. (1원이 2개라서 헷갈리니까 편의상 1a, 1b라고 부르겠다.)

 

💰 1a원을 꺼내고, 만들 수 있는 금액 체크

지금까지 만들어둔 금액: 0원

1a원을 꺼냄으로써 만들 수  있게 된 금액: 1원

 

💰 1b원을 꺼내고, 만들 수 있는 금액 체크

지금까지 만들어둔 금액: 1원

1b원을 꺼냄으로써 만들 수 있게 된 금액: 1b=1원, 1+1b=2원

 

💰 2원을 꺼내고, 만들 수 있는 금액 체크

지금까지 만들어둔 금액: 1원, 2원

2원을 꺼냄으로써 만들 수 있게 된 금액: 2=2원, 1+2=3원, 2+2=4원

 

💰 3원을 꺼내고, 만들 수 있는 금액 체크

지금까지 만들어둔 금액: 1원, 2원, 3원, 4원

3원을 꺼냄으로써 만들 수 있게 된 금액: 3=3원, 1+3=4원, 2+3=5원, 3+3=6원, 3+4=7원

 

💡 이쯤 적어보니, 규칙이 보이기 시작했다.

 - 현재 만들어둔 금액 중 최댓값은 7원이다.

 - 이 상태에서 n원짜리 동전 하나를 새로 꺼내면, n ~ n+7원까지의 돈을 모두 만들 수 있게 된다.

 - 즉, n원짜리 동전 하나를 꺼내고 나면 1~7, n~n+7원을 만들 수 있게 된다.

 

  - n이 8보다 작거나 같다면, 우리는 1 ~ 14원까지 모두 만들 수 있게 된다.

 

✅ 그런데, n이 8보다 큰 수라면 어떨까?  예를 들어 n의 값이 9라면 어떻게 될까?

 

💰 9원을 꺼내고, 만들 수 있는 금액 체크

지금까지 만든 금액: 1원 ~ 7원

9원을 꺼냄으로써 만들 수 있게 된 금액: 9원 ~ 16원

 

 

 - 이렇게 되면 8원은 만들 수 없게 된다.

 - 따라서 정답은 8이다.

---

이제 코드를 짜보쟈.

 

1. 동전을 작은 단위부터 하나씩 꺼내며, target을 아래와 같이 갱신해준다.

        target = 현재 동전을 꺼내서 만들 수 있는 금액의 최댓값 + 1

2. 새로 꺼낸 동전이 target보다 크다면 target은 만들 수 없다. --> 정답

 

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

target = 1
for i in coins:
  if i > target:
    break
  target += i

print(target)

 

 

솔직히 이해하는데 시간이 꽤 많이 걸렸던 문제이다. 나 바보