[백준] 동전 0 : 11047번 - Python

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

11047번: 동전 0

 

 

 

문제의 접근 방법

 

- 입력받은 동전의 가치를 내림차순 정렬하기

- 처음에 입력받은 K원을 만들기 위해서 동전의 가치 A의 값들이 K보다 작은 상태에서 비교해야 함

- K를 A로 나눈 몫을 필요한 동전의 개수에 카운트 해주고 남은 값을 저장해서 그 값을 가지고 위 과정 반복하기

 

 

 

문제 풀이 방법

 

(1) 동전의 종류(N), 만들어야할 값(K)를 입력받기

(2) 동전의 가치들 A를 N개 입력받아 빈 리스트 arr에 추가하기

(3) 필요한 동전 개수의 최솟값을 계산하기 위해 리스트 arr를 내림차순 정렬한 후 count 변수 선언하기

(4) 만약 K원이 arr의 첫 번째 요소보다 크다면, 그대로 arr의 요소들을 앞에서부터 차례대로 나눈 몫을 count에 저장해주고 그 나머지를 가지고 위의 과정 반복하기

(5) 만약 K원이 arr의 첫 번째 요소보다 작다면, 그 요소를 삭제해주고 다시 반복문 continue

(6) count 출력해주기

 

 

 

소스코드

# 두 번째로 풀었을 때(더 나은 코드)
import sys
input = sys.stdin.readline

N,K = map(int, input().split())
A = [int(input()) for _ in range(N)]
A.reverse()

cnt = 0

for i in range(N):
    cnt += K // A[i]
    K %= A[i]
    
print(cnt)



# 처음 풀었을 때
N,K = map(int, input().split())

arr = []
for _ in range(N):
    A = int(input())
    arr.append(A)

arr.sort(reverse=True)

count = 0
for _ in range(len(arr)):
    if K > arr[0]:
        for i in arr:
            count += K // i
            K %= i
        break
    elif K < arr[0]:
        del arr[0]
        continue

print(count)