그리디 알고리즘 1: 거스름돈 구하기

화승이·2023년 3월 20일
0

그리디 알고리즘

  • 그리디 알고리즘
    * 단어 그대로 "탐욕법" 이라고 하며, 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
    (그리고 요즘 코딩테스트에서 자주 나오는 유형으로 뽑힌다.)

  • 오늘 풀어본 유형은 "거스름돈 구하기" 문제이다
    - 문제 풀이는 파이썬으로 진행하였다.

1. 코드업 3301

문제설명

어떤 가게의 욕심쟁이 점원은 거스름돈을 나눠줄때 거스름돈의 개수를 적게해서 주고자 한다.
거스름돈을 입력 받아 점원이 줄 수 있는 최소 거스름돈의 개수를 출력하시오.
예를 들어 54520원인 경우, 거스름돈으로 50000원권 1장, 1000원권 4장, 500원 1개, 10원 2개 해서 총 8개이다.

(※ 현재 우리나라가 사용하고 있는 화폐를 사용한다. 10원 50원 100원 500원 1,000원 5,000원 10,000원 50,000원)

입력 예시
n = 54520 원 일때, 출력은 8


  • 정답
# 그리디 문제 예제 1 거스름돈 구하기
# 코드업 3301 : 거스름돈
# 거스름돈이 n원이라고 입력될 때, 50000원부터 10원까지 최소 개수로 줘야한다. 

# 거스름돈과 거스를 수 있는 화폐의 종류
n = int(input())
list = [50000, 10000, 5000, 1000, 500, 100, 50, 10]

# print 해야할 변수
count = 0

for money in list:
    count += n // money # 50000원부터 거스를 수 있는지 확인
    n = n % money
    
print(count)
    

2. BAEKJOON 5585

문제설명

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

입력예시
n = 380 일 때, 4 출력 / n = 1 일 때, 15 출력


n = 1000 - int(input())
list = [500, 100, 50, 10 , 5, 1]
count = 0

for money in list:
    count += n // money
    n = n % money

print(count)

오늘의 다짐

약간의 일기를 쓰자면 2022.08.22 공군을 입대했다. 그동안, 군대가기전에 코딩에서의 시간을 버리고, 스스로 나태한 시간을 가졌던 것 같은데 앞으로 매일 한 개씩 올리면서 나의 velog의 잔디밭을 꾸미는 시간을 가져보도록 하겠다.

profile
이제부터 하고싶은것만 하면서 살거야

0개의 댓글