[알고리즘/파이썬] 백준 알고리즘 11047번, 동전 0

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

11047번: 동전 0

문제 정리

문제는 간단하다. 총 N 종류의 동전을 가지고, 각 동전을 이용해서 K 원을 만들 때 필요한 동전 개수의 최솟값을 구하는 것.

동전의 가치는 오름차순으로 들어온다.

문제 풀이

- 동전이 들어올 때, 1부터 들어오기 때문에 K원을 만들 수 없는 경우는 없다.

- K원을 만들기 위한 최소값을 구하기 위해서는 큰 가치를 가진 동전부터 채워가면 된다.

- 동전이 오름차순으로 들어오기 때문에, 리스트의 끝 부터 값을 넣어주거나 탐색 시 뒤에서부터 탐색해주면 된다.

코드

N, K = map(int, input().split())
coins = []

for i in range(N) :
	coins.append(int(input()))

cnt = 0

for i in range(N) :
	if K >= coins[N - i - 1] :
		cnt += K // coins[N - i - 1]
		K %= coins[N - i - 1]

print(cnt)

+ ) 풀다가 느낀점

- 처음에는 sort 를 이용해서 내림차순으로 정렬을 해줬는데, 그럴 필요가 없다는 걸 알았다.

- 그래서 둘 다 해봤는데 시간 차이는 크게 없었다.

- 파이썬 sort 알고리즘의 탐색 시간이 nlog(n)이라서 크게 영향을 미치지 않는 건가 싶기도 하고.

- 시간..줄이고 싶다.....