[코테 챌린지] 9일차. 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

- 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.
- 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

---

📌 문제 탐색하기 

우리가 문제를 이해해가는 과정을 작성하시면 됩니다.
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 등을 작성해주시면 됩니다.

알고리즘 선택

• "언제나 거스름돈 개수가 가장 적게 잔돈을 준다." 문장에서 현재 시점에서 가장 좋은 선택(=가장 큰 단위의 동전을 먼저 사용)을 하는 greedy 알고리즘을 사용하는게 적절할 것 같았다.
• 현재 가장 큰 단위의 동전을 먼저 사용하면 남은 거스름돈의 액수가 줄어들고, 그 다음 큰 단위의 동전을 사용할 수 있다. 그래서 현재 선택이 전체 최적해에 포함되기 때문에 greedy 알고리즘을 사용해도 된다고 생각했다. 
• 동전의 종류가 몇 개 되지 않는 상황에서 greedy 알고리즘은 복잡한 계산 없이도 최소 동전 수를 보장할 수 있다.
• 동전의 종류만큼 반복하는 코드라서 시간 복잡도는 O(N)으로 계산이 된지만, 이것도 동전의 종류가 몇 개 되지 않아서 연산량이 적어서 효율적이다.

Greedy Algorithm 특성

• 최적 부분 구조 : 문제의 최적해가 부분 문제의 최적해로 구성될 때
• 탐욕적 선택 속성 : 전체 문제를 해결하기 위해 가장 좋아보이는 선택을 반복하면서 최적해를 보장할 때

---

📌코드 설계하기 

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡으셨을 것 같습니다.
이제 문제 풀이를 본격적으로 하기 전, 이 문제를 풀기 위한 로드맵을 그려보겠습니다.
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성해주시면 됩니다.
처음에는 어려울 수 있지만, 문제를 풀기 전 미리 지도를 그린다라는 생각으로 적어나가 보시면 좋을 것 같습니다 :)

• 타로가 지불할 돈을 입력받는다.
• 사용할 변수 정의
  (1). 카운터에서 지불한 돈 정의(1000엔)
  (2). 잔돈 종류 리스트로 정의 (잔돈이 큰 순서대로 정렬)
  (3). 잔돈 개수를 더하는 변수 정의 
• 잔돈 계산 (카운터에서 지불한 돈 - 타로가 지불할 돈)
• 잔돈 종류가 큰 순서대로 실제 계산되어야하는 잔돈을 나눠준다. 
• 4번에서 계산된 몫은 change_cnt변수(잔돈개수)에 더해주고, 나머지는 change변수(잔돈)로 업데이트 해준다.

---

📌 시도 회차 수정 사항 (Optional)

- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

 

시도1

• 변수명 헷갈리지 않게 여러번 수정하다보니.. 업데이트 해야할 잔돈의 변수명을 잘못 입력했다. 

price = int(input())
pay = 1000

coins = [500, 100, 50, 10, 5, 1]
change_cnt = 0 

change = pay - price
for i in coins:
    c, d = divmod(change, i)
    change_m = d			## 틀린 부분 : change_m이 아니라 change 변수명으로 수정 필요
    change_cnt += c

print(change_cnt)

---

📌정답 코드

# 1. 타로가 지불할 돈을 입력받는다.
price = int(input()) 

# 2. 사용할 변수 정의
# 2-1. 카운터에서 지불한 돈 정의(1000엔)
pay = 1000

# 2-2. 잔돈 종류 리스트로 정의 (잔돈이 큰 순서대로 정렬)
coins = [500, 100, 50, 10, 5, 1]

# 2-3. 잔돈 개수를 더하는 변수 정의 
change_cnt = 0 

# 3. 잔돈 계산 (카운터에서 지불한 돈 - 타로가 지불할 돈)
change = pay - price

# 4. 잔돈 종류가 큰 순서대로 실제 계산되어야하는 잔돈을 나눠주고, 
# 몫은 change_cnt변수(잔돈개수)에 더해주고, 나머지는 change변수(잔돈)로 업데이트 해준다.
for i in coins:
    c, change = divmod(change, i)
    change_cnt += c

print(change_cnt)