[백준/BOJ/11047] 동전 0

11047 | 동전 0

문제 접근 & 설계

1. 동전의 종류가 주어진다.

2. 최소 동전의 개수로 주어진 수를 완성해야한다.

• 최소 동전이면 값이 더 비싼 동전으로 채우는 것이 유리하다. -> 탐욕법

1. 가장 큰 동전부터 주어진 수 K에서 빼본다.

2. 만약 결과가 음수라면, 다음 작은 동전 값을 뺀다.

3. K에서 동전값을 빼서 0보다 같거나 큰수이면 K에서 동전값을 나누고, 나머지를 K에 저장해서 다시 반복한다.

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

사용한 스킬

시간 복잡도

• for : O(n)

O(n)

개선

궁금점

• 탐욕적 속성이 있는가?
  • 값이 큰 동전으로 이루어질 수록 동전의 개수가 무조건 적은가?
  • 탐욕해 = 최적해이어야 한다.

• 문제의 조건을 보자

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

• Ai는 Ai-1의 배수이다. 이것을 잘 생각해보면 50원, 100원이 있을 때, (100원은 50원의 배수) K가 100원이면 무조건 50원 두개보다 100원짜리 한 개가 유리하다. 이런 이유로 무조건 값이 큰 동전으로 구성되는게 무조건 최적해이다. 그렇기 때문에 이 문제는 탐욕적 속성을 갖는다.

난이도

난이도	정답률(%)
실버2	52.492%

알고리즘 분류

• 그리디

소스코드 📃