<Greedy> 백준 11047번. 동전0

문제 출처 : https://www.acmicpc.net/problem/11047

11047번: 동전 0

이 문제가 왜 그리디 알고리즘일까?

 

이 부분에 집중해야 한다. Ai는 A(i-1)의 배수이므로 그리디 알고리즘이 적용되야한다는 것을 알 수 있다.

 

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

for i in reversed(range(N)):
  if(K//coin_list[i]<1):
    continue
  
  else :
    a = K//coin_list[i]
    count += a
    K = K%coin_list[i]


print(count)

내 코드이다. 쉬우니 설명은 생략한다

 

다른 사람들의 코드를 살펴봤는데,

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)

반복문을 거꾸로 돌면서 count에 K//coin_list[i]만큼 더해주고 나머지를 K에 대입하면 된다. 조건문이 필요없는 이유는, 조건에 부합하지 않을 때, K//coin_list[i] 몫이 0이기 때문이다 ㅠ..이걸 생각하지 못한 나는 멍충이..

 

파이썬은 코테 준비하면서 처음 공부하는데, 언어도 매우 쉽고 너무 재미있다! 근데 코테까지 얼마 남지 않았는데 처음 공부해서 너무너무 불안하다 흑흑