백준 코딩테스트 문제 : 동전 0 [실버 3단계, 그리디 알고리즘]

 

[문제]

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

동전을 적절히 사용해서 그 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하라.

 

** 풀이: 가장 큰 동전 종류부터 합 K에 대한 몫을 카운트하고 같은 방법으로 나머지 동전을 내림차순으로 처리한다.

 

[입력]

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

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

** 풀이: 괄호친 조건은 큰 동전이 항상 작은 동전의 배수라는 의미이다. 이 조건으로 인해 그리디 알고리즘을 사용할 수 있다.

 

 

[출력]

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

[문제 풀이]

1) 그리디 알고리즘을 사용한다.

2) 가장 큰 동전부터 몫을 카운트하고 나머지 동전도 똑같이 내림차순으로 처리한다.

3) 2)의 방법으로 K에서 몫*동전종류 만큼 빼주며 전체 합 K가 0이 될 때까지 반복문을 돌린다.

 

[유의점]

*주의할 점은 각 종류의 동전을 한번씩 빼면 안된다는 것이다.  배수로 뺄 수 있는 것은 한번에 처리해야한다. 

 즉, 몫*동전종류를 사용해서 처리해야함. --> 그리디 알고리즘

 

ex. K=250 이고, 빼려는 동전이 100원짜리일때

-100, -100 ==> X, 2번처리. 시간초과. 

-100*2  ==> 0, 1번 처리. 

 

 

[첫 시도 코드]

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

처음에 적은 시간 초과된 코드. 배수로 처리하지 않고 하나씩 처리함.

 

 

[정답 코드] - 2개 (로직은 같음) 

** 시간초과되지 않은 코드. 주석으로 설명.

n, k = map(int,input().split()) # 동전의 종류 = n, 만들어낼 합 = k
coin = [] # 동전의 종류를 입력받을 리스트
for i in range(n): # 반복문으로 리스트 입력받음
    coin.append(int(input()))
    
count=0 # 동전 개수의 최솟값 담는 count

i=n-1 # 배열 역순으로 돌리기 위해 i 변수 지정
while k!=0:
    if k//coin[i]>0: # 몫이 있으면 
        count += k//coin[i] # 몫만큼 처리하기때문에 그대로 더해줌
        k -= (k//coin[i])*coin[i] # 몫 * 동전종류
    i-=1 # 다음 동전 종류로 넘어감
    
print(count) # 결과 출력

코드 길이: 224

N, K = map(int, input().split()) 
coin_lst = list()
for i in range(N):
    coin_lst.append(int(input()))

count = 0
for i in reversed(range(N)):
    count += K//coin_lst[i] #카운트 값에 K를 동전으로 나눈 몫을 더해줌
    K = K%coin_lst[i] # K는 동전으로 나눈 나머지로 계속 반복

print(count)

코드길이 : 322

 

 

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

11047번: 동전 0