백준_11047_동전 문제

문제 출처

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

11047번: 동전 0

해결(코드)

단순한 그리디 알고리즘 문제이다.

# 동전 갯수 , 목표 액수  받기
input_list = input().split()
N = int(input_list[0])
K = int(input_list[1])

# 동전 개수 만큼  배열 생성
coin_list = [0] * N
# 빈리스트로 생성 해서 append해도 되지만 4ms 시간이 더 걸림
#coin_list = []

# 동전 개수 만큼 반복해서 입력 받기
for idx in range(N):
    coin_list[idx] = int(input())
    #coin_list.append(int(input()))
    # 받은 동전의 단위가 목표 액수 보다 크면 필요 없으므로 인덱스 번호를 저장하고 
    # 반복문에서 나온다.
    if(coin_list[idx]>K):
        N=idx
        break
# 결과 변수
result = 0

# 제일 큰 동전 부터 사용하기 위해 배열의 제일 끝(N-1) 부터 0까지 역순으로 호출한다.  
for idx in range(N-1,-1,-1):
    # 동전으로 목표액 나눈 몫
    result += K//coin_list[idx]
    # 동전으로 목표액 나눈 나머지
    remain_k =  K % coin_list[idx]
    # 완벽히 나눠지면 반복 종료
    if remain_k == 0:
        print(result)
        break
    # 아니면 나머지를 다음으로 작은 동전 단위로 나눔
    K = remain_k