[그리디 알고리즘] 11047번 동전0 풀이(파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 백준에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다.

그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다.

 

[접근 방식]

- 문제에서 요구하는 역량은 무엇인지?

- 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다.

 

- 백준 문제 링크입니다. : https://www.acmicpc.net/problem/11047

11047번: 동전 0

아래 작성된 답안은 제가 직접 작성 후 백준 페이지에서 채점하여 정답으로 인정된 답안입니다.
공식 답안이 아니므로 최적의 해가 아닐 수 있으며, 답안은 다른 분들과 상이할 수 있습니다.

 

[풀이]

n, k = map(int,input().split())
coin = []
for i in range(n):
    a = int(input())
    coin.append(a)
count = 0
for i in coin[::-1]:
    if k//i == 0:
        pass
    else:
        count += k // i
        k -= (i*(k//i))
print(count)

먼저 n(동전의 종류)와 k(목표값)을 사용자로부터 입력받을 수 있도록 작성했습니다.

이후 for문을 이용하여 n번만큼 사용자에게 값을 입력받도록 하였고, 입력받은 값은 모두 coin이라는 리스트에 정리해두었습니다.

 이후 for문을 활용하여 coin 리스트를 역으로 받았고, 리스트 요소값과 k(목표값)을 비교하여 몫이 1이상이 되는 경우에만 몫만큼 count 하도록 하였습니다.

왜냐하면 만약 몫이 0이라는 것은 k값보다 i(동전의 금액)이 더 크다는 의미이고, 이는 곧 k값을 맞추기위해 해당 동전을 사용할 수 없다는 의미이기 때문입니다.

순서대로 진행하여 k값보다 i 값이 더 작아져 count가 된다면, k의 값을 count한만큼 줄여줘야하므로 count된 동전금액 x 몫 만큼 현재 k 값에서 빼주었습니다.

 

감사합니다.