11047번 동전 0 with python3

 

 

1) 사이트

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

2) 문제

이렇게 생각하면 된다.

내가 내야할 가격이 4200원이 있는데, 내 수중에 가진 동전들을 최소한으로하여 지불하는 것이다.

 

 

3) 파이썬 코드

#1. 첫째줄에 N, K 주어진다.
n,k=map(int,input().split())

#2. N개의 줄에 각각 동전의 가치(value)가 오름차순으로 주어진다.
#2-1.value 리스트를 int로 꾸리기
value=[]
for _ in range(n):
  value.append(0)

#2-2.동전의 가치 입력
for i in range(n):
  value[i]=int(input())


#3. 최소의 동전 개수를 만들기 위해 가장 큰 값(큰 인덱스)부터 적당한 가격선을 찾는다.
result=0
for i in range(n-1,-1,-1):
  #k 목표값보다 작은 동전을 고르기
  if k>=value[i]:
    result+=k//value[i]
    k=k%value[i]
  else:
    continue
print(result)

 

오답의 이유

나는 이 문제를 1번 오답으로 냈는데, 3번 문단 코드 중 최적의 value를 찾아내는 과정에서

if k > value[i]라고 제출했기 때문이다.

 

반례로 아래와 같은 케이스를 입력하면 답이 1이 나와야하는데, 같음(>를 >=로)의 표시를 안해줘서 답이 2로 도출되었다. (1이 2번 들어가서...) 같음(>=)표시 후 2가 인식되어 제대로 결과 1이 나왔다.

 

(입력)

2 2

1

2

 

(결과)

1

 

---

걸린 시간 16분