[ 이코테 ] 만들 수 없는 금액 - 파이썬(Python)

문제

• N개의 동저전을 이용하여 만들 수 없는 양의 정수 중 최솟값 구하기

입력 예시

5
3 2 1 1 9

출력 예시

8

예시 풀이

n = 5
coin = [ 1, 1, 2] #오름차순 정렬

1원: 1
2원: 2
3원: 1 + 2

• 4원도 만들 수 있는지 확인
• 이때 화폐 단위 3원 동전 추가
  coin = [ 1, 1, 2, 3]
  4원: 1 + 3
  5원: 2 + 3
  6원: 1 + 2 + 3
  7원: 1 + 1 + 2 + 3
• 8원도 만들 수 있는지 확인
• 이때 화폐 단위 9원 동전 추가
  coin = [ 1, 1, 2, 3, 9 ]
  8원: x
  9원: 9
• 8원을 만드는 방법이 존재하지 않음
• 정답: 8

아이디어

1. 동전을 오름차순 정렬
2. 1부터 차례대로 특정한 금액을 만들 수 있는지 확인
   • 1부터 target - 1까지의 모든 금액을 만들 수 있다고 가정
   • 현재 확인하는 동전을 이용해 target 금액을 만들 수 있는지 확인

코드

n = int(input())

coin = [0] * n
coin = list(map(int, input().split()))

coin.sort()
target = 1

for i in coin:
    # target 보다 큰 숫자의 coin이 들어올 경우, 만들 수 없는 금액 찾음
    if target < i:
        break
    
    # target - 1 까지 만들 수 있음
    target += i

print(target)

1. target과 coin에 들어있는 동전들을 하나씩 비교
2. target > i 일 경우, target += i를 진행하여 그 target - 1 까지의 모든 금액을 만들 수 있음
3. target < i 일 경우, 만들 수 없는 금액을 찾음

책도 보고 여러 블로그도 찾아서 이해하려 했는데 잘 이해가 가지 않는다..
다음에 다시 풀어봐야할 것 같다.