블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 11047번: 동전 0을 풀고 작성한 글입니다.
문제
설명
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
풀이
접근법
주어진 K 보다 작거나 같은 동전들을 내림차순 정렬한 뒤 해당 K 를 동전들로 차례로 반복하여 나눠주면서 몫은 곧 횟수가 되고 나머지는 다시 K 가 된다.
전형적인 그리디 알고리즘 문제로 가장 큰 경우의 수부터 반복문을 시작하면 풀리는 문제다.
나의 풀이
접근법을 바탕으로 푼 코드는 아래와 같다. 이때 첫 번째 for 반복문에서 이미 A 라는 리스트에 조건에 충족하는 동전 입력값을 insert() 메서드를 활용하여 0 번째 배열에 삽입한 이유는 sort() 메서드 또는 내장함수 sorted() 의 경우 최악의 상황에서 O(NlogN)의 시간 복잡도를 가지는 데 반해 아래와 같은 형태는 무조건적으로 O(N)을 보장하기 때문이다.
N, K = list(map(int, input().split(" ")))
A: list[int] = []
for _ in range(N):
coin: int = int(input())
if coin <= K:
A.insert(0, coin)
answer: int = 0
for coin in A:
answer += (K // coin)
K %= coin
print(answer)Big-O
입력값을 받는 상황에서 if 조건문과 insert() 내장함수를 활용해 이미 내림차순 정렬을 해두기 때문에 여기서 N 만큼 for 반복문을 수행해야 하니 결국 시간 복잡도는 O(N)이다.
