[알고리즘] 백준 11047 : 동전 0 - S4

2023.04.03 풀이

import sys
input=sys.stdin.readline
arr=[]
t=0
cnt=0

n,k=map(int, input().split())
for i in range(n):
    a=int(input())
    arr.append(a)
    if t>k:
        t=i
    
while True:
    if k==0:
        break
    cnt+=k//arr[i]
    k%=arr[i]
    i-=1

print(cnt)

• 그리디 알고리즘 활용
• 주어진 값(k) 보다 큰 값을 기억하기 위해 t에 i저장.n보다 큰 값보다 한 칸 작은 값으로는 무조건 나눠지기 때문
• while 문 안이 약간 헷갈렸는데, 주어진 값(k)을 나눠준 몫을 cnt(개수)에 합.
• k는 나눠준 나머지 값으로 업데이트
• k보다 작은 값으로 나눠준 몫이나 나머지는 영향 x

다른 풀이

import sys
input = sys.stdin.readline

N, K = map(int ,input().split())
coin = []
for _ in range(N):
    coin.append(int(input()))
coin.sort(reverse= True)

cnt = 0
for num in coin:
    if K >= num:
        cnt += K // num
        K = K % num

print(cnt)

check point

• 그리디 알고리즘 : 가장 큰 값 부터 나눠주기