11047. 동전 0 (Silver IV)

✔️ 문제

11047번 문제 보기

✔️ 문제 분석 및 해결 과정 설계

• 문제 이해 :

  • 가지고 있는 동전 종류 : N가지 (매우 많이 가지고 있음)
  • 동전의 합을 K로 만들고자 함
  • 동전 개수의 최솟값 구하기

• 입력 :

  • 첫째 줄 : N K (1 <= N <= 10, 1 <= K <= 100,000,000)
  • 둘째 줄 : N개의 줄에 동전의 가치 $A_i$가 "오름차순"으로 주어짐
    • (1 <= $A_i$ <= 1,000,000, $A_1$ = 1, i >= 2인 경우 $A_i$는 $A_i-1$의 배수)

• 출력 :

  • 첫째 줄의 K원을 만드는데 필요한 동전 개수의 최솟 값 출력

• 문제 분석

  • N의 조건(1 <= $A_i$ <= 1,000,000, $A_1$ = 1, i >= 2인 경우 $A_i$는 $A_i-1$의 배수)을 통해 본 문제는 그리디로 해결
    • 최적 부분구조 충족
    • 탐욕스러운 선택 속성 충족
  • 동전의 나머지 값이 0일 때까지 반복
    • 큰 동전부터 차례로 나머지를 사용해 0

✔️ 문제 해결 과정

1. N과 K 입력

• map(type, 값)

N, K = map(int, input().split())

2. 가장 큰 동전부터 사용하기 위해 coins배열 reverse()

N, K = map(int, input().split())
coins = [int(input())for _ in range(N)]
coins.reverse() # 역순으로 코인 사용

3. 동전의 개수는 ans 변수에, 남은 금액은 K에 갱신

N, K = map(int, input().split())
coins = [int(input())for _ in range(N)]
coins.reverse() # 역순으로 코인 사용
ans = 0

for coin in coins:
    ans += K // coin
    K %= coin

print(ans)

💡 회고

11047은 그리디 알고리즘의 가장 쉬운 대표 문제이다.
먼저 본인이 작성한 코드이다.

N, K = input().split()
N = int(N)
K = int(K)
rmnd = K # 나머지 값을 저장하는 변수 
coin_count = 0 # 동전 개수를 저장하는 변수 

coin_type = [int(input()) for _ in range(N)] # 동전 종류 입력 
for i in range(N-1, -1, -1): # 인덱스 접근 N-1 ~ 0
    if coin_type[i] <= rmnd: # 동전 금액이 남은 금액보다 작은 경우에 한함
        coin_count += rmnd // coin_type[i]
        rmnd = rmnd % coin_type[i]

print(coin_count)

처음 코드를 작성했을 때에는 for i in range(N-1, 0, -1)으로 설정해 주었었고,
for문 안에서 coin_count를 체크해주는 분기문 조건을 if coin_type[i] < rmnd로 설정했었다.

자꾸 너무 바보같은 실수로 오답이 된다 ... 😅
모든 테스트케이스에서 같은 정답이 나옴에도 틀렸다고 뜨는데 역시 컴퓨터는 정확하다.
python의 for _ in range()문은 range(1, 10)일 때 1 ~ 9까지(두번째 인자 값 -1까지 적용(양수의 경우)) 적용되는데,
본인은 코드에서 두번째 인자 값을 0으로 설정했기에 가장 큰 단위의 코인부터 가장 작은 단위의 코인보다 하나의 윗 단위까지만 적용된 것이었다.

두번째 실수는 coin_type[i] < rmnd로 설정해주었기에 coin_type[i]이 rmnd와 같은 경우
count 누적을 해주지 못한다는 부분이다.
코딩테스트 준비 하면서 내 신중함을 돌아보게 되고 문제 분석을 더욱 명확히 해야함을 느낀다!
여러모로 굳 ...

마지막으로 강의에서의 코드 접근방식을 통해 python에서 알아두면 정말 유용한 메소드들을 많이 얻어가게 되었다.

N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
coins.reverse() # 역순으로 코인 사용

ans = 0

for coin in coins:
    ans += K // coin
    K %= coin

print(ans)

본인의 경우 반복문을 역순으로 돌려 coin_type을 체크해주었지만,
배열 리스트에 값을 넣어주고 ARRAY.reverse()를 통해 역순으로 정렬할 수 있었고
그 결과 로직 부분의 코드가 훨씬 명료해짐을 알게 되었다!

로직을 직관적이게 짜야 디버깅도 쉬워짐을 배운 문제이다.