파이썬을 이용해서 그리디 문제 풀기

 

 

 

 

 

 

<<1번. 거스름 돈>>

문제: 음식점의 계산을 돕는 점원이 있다. 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요.

•참고 : 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

•참고 : 500원, 100원, 50원, 10원짜리 동전은 무한이 존재한다.

 

 

<<문제 풀이 방식>>

1. 문제 이해하기

2. 코드 작성하기

 

 

 

1. 문제 이해하기

 

만약 1260원을 거슬러줘야 할 경우

1. 가장 큰 동전부터 거슬러주기 (500원 , 100원 , 50원 , 10원 순서대로)

•500원 2개 -> 260원 남음

•100원 2개 -> 60원 남음

•50원 1개 -> 10원 남음

•10원 1개 -> 0원 남음

이 방법의 경우 6개의 동전을 사용해서 모든 돈을 거슬러 줄 수 있음

 

2. 가장 작은 화폐부터 거슬러주기 (10원 , 50원 , 100원 , 500원 순서대로)

•10원 126개 ->0원 남음

 

•50원 25개 -> 10원 남음

•10원 1개 -> 0원 남음

 

•100원 12개 -> 60원 남음

•50원 1개 -> 10원 남음

•10원 1개 -> 0원 남음

 

10원부터 시작하면 126개 , 50원부터 시작하면 26개 , 100원부터 시작하면 14개의 동전이 필요하다

 

즉 1번의 경우인 가장 큰 동전부터 거슬러 주는 경우가 최적의 경우라는 것을 알 수 있음!! 

 

 

2. 코드 작성하기

 

n = int(input('거스름돈을 가격(정수)으로 입력해 주세요 :'))  <-  먼저 거슬러줘야 할 돈 입력하기
count = 0 

array = [500, 100, 50, 10]  <- 가지고 있는 동전 입력하기 
for coin in array:
    count += n // coin  <- 거슬러 줄 수 있는 동전 갯수 세기 
    n %= coin

print('동전의 거스름돈 최소 개수는 :', count)  <- 결과 출력

 

 

n = int(input('거스름돈을 가격(정수)로 입력해 주세요 :')) 

count = 0

array = [500, 100, 50, 10] 

for coin in array:

    count += n // coin 

    n %= coin

   

print('동전의 거스름돈 최소 개수는 :', count)

 

출력

 

 

 

<<2번. '1' 만들기>>

 

•문제 : N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택 수행하는 방법은? 최소값을 출력하시오.

•참고 : 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

•참고 : N에서 1을 뺀 후, N을 K로 나눈다.

 

 

 

1. 문제 이해하기

 

 -1과 나누기 K만 이용해서 N을 1로 만드는 최적의 경우 찾기

 

ex) N=17 , K=4  

1. 17-1 =16

2. 16/4 = 4

3. 4/4 =1 

총 3번 

 

ex) N=16 , K=4

1. 16/4 =4

2. 4/4 = 1

총 2번 (-1을 사용하지 않아도 될 경우엔 사용하지 않아도 됨)

 

 

 

2. 코드 작성하기

 

n, k = map(int, input('두 수를 공백으로 분리하여 입력 : ').split())  <- N과 K값 입력받기
result = 0

 

 

while True: 
    target = (n // k) * k   <- N=16 , K=4인 경우 처럼 나누어떨어지는 경우 
    result += (n - target)  <- N=17 , K=4인 경우 처럼 나누어 떨어지지 않는 경우
    n = target 
  

  if n < k:  <- 더 이상 나눌 수 없을 때  while문 중지
        break
   

 result += 1 
    n //= k  <- k로 나누기
result += (n - 1)  <- 나누어 떨어지지 않는 경우 1 빼기

print('1이 도달하기까지 연산 횟수 :', result)  

 

n, k = map(int, input('두 수를 공백으로 분리하여 입력 : ').split()) 
result = 0
while True: 
    target = (n // k) * k 
    result += (n - target) 
    n = target 
    if n < k: 
        break
    result += 1 
    n //= k 
result += (n - 1) 

print('1이 도달하기 까지 연산 횟수 :', result)