[알고리즘] 탐욕법(Greedy) 유형별 문제풀이

문제 1 : 거스름돈

거스름돈 500원, 100원, 50원, 10원 동전이 무한히 존재할 때,
손님에게 거슬러줘야할 돈이 N원일 때 거슬러줘야할 동전의 최소개수는?

N = int(input()) # 1260
coin = [500, 100, 50, 10]
cnt = 0

for i in coin :
    cnt += N//i
    N = N%i

print(cnt)
>>> 6

문제 2 : 큰 수의 법칙

큰 수의 법칙은 다양한 수로 이뤄진 배열이 있을 때, 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징이다. 배열의 크기 N, 숫자가 더해지는 개수 M, 그리고 K가 주어질 때 큰 수의 법칙에 따른 결과는?

n, m, k = map(int, input().split()) # 5, 8, 3

d = list(map(int, input().split())) # [2, 4, 5, 4, 6]
d.sort() # 내림차순 : [6, 5, 4, 4, 2]
# 이 문제의 핵심은 가장 큰 수, 두 번째로 큰수
first = d[n-1] # 가장 큰 수
second = d[n-2] # 두 번째로 큰 수
result = 0 

while True:
  for i in range(k): # 가장 큰 수 k번 더하기
    if m == 0 :
      break    
    result += first
    m -= 1 # 더할 때마다 1씩 빼기 : 3번 반복하면 0이되고 break
   
  if m == 0:
    break
  result += second # 두 번째로 큰 수를 한 번에 더함
  m -= 1 # 더할 때마다 1씩 빼기 : 8번 반복하면 0이되고 break

print(result)
>>> 46

문제 3 : 숫자 카드 게임

숫자 카드 게임은 여러 개 숫자 카드 중, 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임으로, 게임을 룰을 지키며 카드를 뽑아야 하며 룰은 다음과 같다.
1. 숫자가 쓰인 카드들이 N x M 형태로 놓여있다. 이 때, N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함 돼 있는 행을 선택한다.
3. 그 다음 선택한 행에 포함된 카드들 중, 가장 숫자가 낮은 카드를 뽑는다.
4. 따라서 처음 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려해 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

n, m = map(int,input().split())
result = 0
for _ in range(n):
  card = list(map(int, input().split()))
  min_v = min(card)
  result = max(result, min_v)
print(result)

---

문제 4 : 1이 될 때 까지

어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려고 한다. 단, 두번째 연산은 N이 K로 나눠떨어질 때만 선택할 수 있다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
N과 K가 주어졌을 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

n, k = map(int,input().split()) # 25, 5
cnt = 0
while n > 1:
  if n % k == 0:
    n = n//k
    cnt += 1
  else:
    n -=1
    cnt += 1
   
print(cnt)

문제 5 : 곱하기 혹은 더하기

각 자리가 숫자(0~9)로만 이뤄진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인해 숫자 사이에 x 혹은 + 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 구하시오.
단, +보다 x를 먼저 계산하는 일반적 방식과 달리, 모든 연산은 왼쪽부터 순서대로 이뤄진다고 가정함. 예를 들어, 02984라는 문자열로 만들 수 있는 가장 큰 수는 (((((0+2) x 9) x 8) x 4) =576, 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.

n = input()
result = int(n[0]) # 첫번째 문자 숫자로 대입

for i in range(1, len(n)):
	# 두 수 중, 하나라도 0 혹은 1 이면, 곱하기보다는 더하기 수행
	num = int(n[i])
    if num <= 1 or result <= 1:
    	return += num
    # 나머지는 곱하기 수향    
    else: 
    	return *=num
print(result)