[ 이것이 코딩테스트다 with 파이썬 ] Greedy

그리디 (탐욕법)

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

 

1. 거스름돈 (예제)

2. 큰 수의 법칙 (실전문제)

3. 숫자 카드 게임 (실전문제)

4. 1이 될 때까지 (실전문제)

 

[ 예제 1 ] 거스름돈

※ 문제
카운터에는 거스름돈으로 사용할 500원,100원,50원,10원짜리 동전이 무한히 존재한다고 가정한다.

손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야할 동전의 최소 개수를 구하라.

단 N은 항상 10의 배수이다.

# 거스름 돈
n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin  # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기  // : 몫 연산자
    n %= coin  # % : 나머지 연산자

print(count)

출력    6  

 

[ 실전문제 ] 큰 수의 법칙 

※ 문제

배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오 

# 큰 수의 법칙 (처음 작성한 코드)
n, m, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
a.reverse()

renew = [a[0], a[1]]

result = 0

while m >= 1:
    for i in range(k):
        result += int(renew[0])
        m -= 1
    result += int(renew[1])
    m -= 1

print(result)

 

입력   

5 8 3  

2 4 5 4 6 

 

출력    46  

 

--- 풀이 해설 ---

# 큰 수의 법칙 (풀이해설1)
# 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] # 두 번째로 큰 수

result = 0

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

print(result)

# 큰 수의 법칙 (풀이해설2)
# 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)

 

[ 실전문제 ] 숫자 카드 게임 

※ 문제

숫자 카드 게임은 여러 개의 숫자 카드 중에서 자당 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.

단, 게임의 룰을 지켜야 한다.

 

1. 뽑고자 하는 카드가 포함되어 있는 행을 선택 2. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 함3. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략 세우기 

 

카드들이 N (행) x M (열) 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑느 프로그램을 만드시오. 

# 숫자 카드 게임
n, m = map(int, input().split())

result = 0

for i in range(n):
    data = list(map(int, input().split()))
    min_value = min(data)
    result = max(0, min_value)

print(result)

입력   

3 3

3 1 2

4 1 4

2 2 2 

 

출력    2  

 

[ 실전문제 ] 1이 될 때까지 

※ 문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.

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

 

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오

# 1이 될 때까지 (처음 작성한 코드)
n, k = input().split()
n = int(n)
k = int(k)
min = 0

while n >= k:
    while n % k != 0:
        n = n - 1
        min += 1
    n //= k
    min += 1

print(min)

# 1이 될 때까지 (풀이 해설)
n, k = map(int, input().split())
result = 0  # 1, 2

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k  # 25 , 5, 1
    result += (n - target)  # 25 -25 = 0, 5-5 = 0 1-1 =0
    n = target  # 25, 5, 1
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:  # 25, 5, 1
        break
    # K로 나누기
    result += 1
    n //= k  # 25//5 = 5 , 5//5 = 1

# 마지막 으로 남은 수에 대하여 1씩 빼기
result += (n - 1)  # 3-1
print(result)  # 2

# 1이 될 때까지
n, k = map(int, input().split())

result = 0

while True:
    if n % k != 0:
        n -= 1
        result += 1
    else:
        n = n / k
        result += 1
    if n == 1:
        break

print(result)

입력  

25 5

 

출력    2