chapter 3. 그리디

현재 상황에서 지금 당장 좋은 것만 거르는 방법

문제 상에 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준 제시

 

1. 거스름돈

 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라

import sys
input=sys.stdin.readline
 
n=int(input())
coin=[500, 100, 50, 10]
result=0
 
for c in coin:
    if n==0:
        break
    result+=n//c
    n%=c
 
print(result)

 

2. 큰 수의 법칙

입력 예시

5 8 3

2 4 5 4 6 

 

출력 예시

46 

 

* 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5  =  46

 

처음

import sys
input=sys.stdin.readline
 
n, m, k=map(int, input().split()) #합횟수, 연속
arr=list(map(int, input().split()))
arr.sort()
result=0
# print(arr)
while 1:
    result+=arr[-1]*k
    m-=k
    
    if m!=0:
        result+=arr[-2]
        m-=1
    if m==0:
        break
 
print(result)

# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
data = list(map(int, input().split()))
 
data.sort() # 입력 받은 수들 정렬하기
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수
 
# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k# 반복 수열의 나머지 값
count += m % (k + 1)
 
result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기
 
print(result) # 최종 답안 출력

3. 숫자 카드 게임

입력 예시

3 3 

3 1 2

4 1 4

2 2 2

 

출력 예시

2

import sys
input=sys.stdin.readline
 
#행에서 가장 숫자가 낮은 카드 뽑기
#그 중 가장 높은 숫자의 카드를 뽑기
n, m=map(int, input().split()) #행, 열
arr=[]
result=0
for _ in range(n):
    arr.append(list(map(int, input().split())))
 
for i in range(n):
    min_value=min(arr[i])
    if min_value>result:
        result=min_value
 
print(result)

 

 

4. 1이 될 때까지

입력 예시

2 5

 

출력 예시

2

import sys
input=sys.stdin.readline
 
#N에서 1을 뺀다
#N을 K로 나눈다
#N이 1이 될 때까지 수행해야 하는 횟수의 최솟값
 
n, k=map(int, input().split())
result=0
 
while n!=1:
    if n%k==0:
        result+=1
        n//=k
    else:
        n-=1
        result+=1
 
print(result)