[ALGORITHM] 3. 그리디

이것이 취업을 위한 코딩테스트다 python 문제 풀이

3-1. 거스름돈

# C3. GREEDY - 거스름돈

import sys
put = sys.stdin.readline

n = int(put())
count = 0

list = [500, 100, 50, 10]
for coin in list:
    # n - i
    # count =+ 1
    count += n // coin
    n %= coin

print(count)

 

3-2. 큰 수의 법칙

내 풀이

# C3. GREEDY - 실전 문제 '큰 수의 법칙'

import sys
put = sys.stdin.readline

n, m, k = map(int, put().split())
nums = list(map(int, put().split()))
sum = 0

nums.sort(reverse=True)
for i in range(1, m+1):
    if i < k: # i=1인 경우 커버
        sum += nums[0]
    elif i % k != 1: # 제일 큰 수 k번 더하기
        sum += nums[0]
    elif i % k == 1: # k번 다음에 두 번째로 큰 수 더하기
        sum += nums[1]
print(sum)

책 풀이

# 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. 숫자 카드 게임

내 풀이

# C3. GREEDY - 실전 문제 '숫자 카드 게임'

import sys
put = sys.stdin.readline
answer=0
n, m = map(int, put().split())
for i in range(1, n+1):
    nums = list(map(int, put().split()))
    answer_list = min(nums)
    answer = max(answer, answer_list)    
print(answer)

책 풀이 - 2중 반복문 구조 활용

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

 

3-4. 1이 될 때까지

내 풀이

# C3. GREEDY - 실전 문제 '1이 될 때까지'

import sys
put = sys.stdin.readline
n, k = map(int, put().split())
num=0
while n!=1:
    if n%k==0: 
        n=n/k
        num+=1
    else: 
        n=n-1
        num+=1
print(num)

책 풀이 - 단순하게 풀기

# N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0

// N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)

책 풀이

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

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

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