[백준 알고리즘] 백준 11047번 동전 0(Python)

 

안녕하세요, 츄르 사려고 코딩하는 집사!      코집사입니다.

1. 문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

2. 입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

3. 출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

4. 풀이

#값 입력
N, K = map(int, input().split())
Money = [int(input()) for _ in range(N)]

#코인 총 개수 입력 변수
num = 0

#알고리즘
#큰 값이 있는 뒤의 인덱스부터 계산
for i in range(1,N+1): #1
    coin = Money[-i] #2
    if K >= coin: #3
        mok = K//coin #4
        K -= coin*mok #5
        num += mok #6
        
print(num)

이 문제는 최소의 동전 개수를 찾아야하는 문제로, 예제에 나온 것처럼 4,200원일 경우에 1,000원 4개 100원 2개로 하여 총 6개로 나온다.
그리하여 큰 값을 가진 것부터 나누어 구하면 된다.

#1 : 맨 처음에 for i in range(N)으로 생각을 했다가 i가 0부터 시작할 경우 결국 첫 값이 그 자리이기 떄문에 1부터 N+1까지 범위를 설정했다.

#2 : Money라는 리스트에서 -i번째 값을 coin에 저장 -> 결국 큰 값을 저장

#3 : 4,200원에서 5000원을 가져오면 안되니까 if 문을 사용하여 K값보다 작은 값으로 나눌 수 있게 조건문 설정

#4 : 이 코드는 간결하게 하기 위해 사용했다. 원래는 K -= coin*(K//coin)을 하려다가 너무 코드가 더러워서 사용

#5 : 맨 처음 나눴던 값을 빼서 다음 동전을 선택하는 것을 반영하기 위해 빼줌

#6 : 코인의 총 개수를 저장