그리디 알고리즘> 11047. 동전 0

 

<문제링크: www.acmicpc.net/problem/11047>

11047번: 동전 0

문제설명: N개 종류의 동전이 주어지고, N개의 종류별 동전들을 적절히 사용해

그 합을 K로 만드는 동전의 최소 개수를 구하는 문제이다.

 

 

[1차 시도]

N, K = map(int,input().split())
coin = [int(input()) for x in range(N)]

ans = 0
coin_sum = 0
originK = K

for i in range(N-1,-1,-1):
    if coin[i]<= K:
        num = K//coin[i]
        
        K-= coin[i]*num
        coin_sum+=coin[i]*num
        ans+=num
        
    	if coin_sum == originK:
        	break
print(ans)

 

풀이: N,K를 입력받고 N줄에 걸친 동전의 종류들은 coin 배열에 저장한다.

 

다음 동전의 개수를 세어줄 ans와 동전의 합을 구하는 coin_sum을 0으로 설정하고, 

input값으로 주어지는 K를 저장해 줄 original_K 변수를 생성한다.

 

coin 배열이 오름차순으로 주어지므로 뒤에서부터 탐색하귀 위해 for문 range를 설정해주고,

현재 동전의 값이 아직 K(동전합까지 남은 값)보다 작다면 해당 값을 K로 나눈 나머지를 구해서

현재 동전 값*동전 종류의 개수를 K에서 빼준다.

 

예를 들면 예제 1번에서 4200원보다 처음으로 작은 1000에서 멈춰서

4200//1000의 나머지인 4만큼 곱한 4000을 4200에서 빼주는 것이다. 

 

그리고 동전들의 합을 저장하기 위해 coin_sum에 똑같은 값을 더해주고

ans에는 방금 사용한 동전 종류의 개수를 더해준다.

 

그리고 만약 현재까지의 합 coin_sum이 문제에서 주어진 동전의 합 K인 originalK와

일치하다면 break로 반복문을 종료한다. 

 

채첨결과: 정상적으로 잘 통과한다.

 

 

 

 

'쫄보의삽질' 블로그 탄생스토리가 궁금하다면:

Git push 취소 방법 (feat. '쫄보의삽질' 블로그 탄생 배경)