[BOJ] Q1 만들 수 없는 금액

[BOJ] Q1 만들 수 없는 금액

Language: Python

주어진 화폐 단위로 만들 수 없는 금액 중 최소값을 구하는 문제이다.

Example

[3,2,1,1,9] 가 있으면

|Value|Description| |–|–| |1|1| |2|2| |3|3| |4|1+3| |5|2+3| |6|1+2+3| |7|1+1+2+3| 8을 만들 수 없다.

이 문제를 해결하기 위해서는 target 금액을 만들어 낼 수 있냐를 판단할 때, 1~target-1까지의 숫자들은 모두 만들 수 있다는 확정 아래에서 판단한다, 그리고 target을 만들 수 있으면 target을 갱신한다.

target=1 일때, 화폐 단위 1을 만나면, 0은 이미 만들수 있으므로 0+1은 1 target을 만들 수 있다. target+=1

target=2일때, 화폐 단위 1을 만나면, 1은 이미 만들 수 있으므로 1+1로 target을 만들 수 있다. target+=1

target=3일때, 화폐 단위 2을 만나면, 1~2까지는 만들 수 있으므로, 1+2로 target을 만들 수 있고, target+=2

target=5일때, 화폐단위 3을 만나면, 1~4까지는 만들 수 있으므로, 5또한 1~4까지의 조합으로 만들어 낼 수 있다. target+=3

target=8일때, 화폐 단위 9을 만나면, 8을 만들어 낼 수 없다. 1~7까지의 숫자들은 만들 수 있지만, target보다 큰 숫자를 만나버리게 되면 target보다 큰 숫자들만 만들어 낼 수 있다.

따라서 8은 만들어 낼 수 없다.

위의 방식을 이용해서 문제를 해결할 수 있다.

Solution

def solution():
  target=1
  for money_type in money_types:
    if target< money_type:
      break
    target+=money_type
  return target
  
if __name__ == "__main__":
  N=int(input())
  money_types=list(int(input().split()))
  print(solution())