그리디

'이것이 취업을 위한 코딩 테스트다' 참고

 

그리디 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

 

[ 92쪽 큰 수의 법칙 ]

 

My Code

n, m, k = map(int, input().split())
num = list(map(int, input().split()))
num.sort(reverse=True) # 4 3 2 1
print(num)
result = 0

for i in range(m):
    if (i+1)%(k+1)==0:
        result += num[1]
    else:
        result += num[0]

 

책 속 Code

# 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) # 최종 답안 출력

• count에 대한 코드를 따로 만들어 반복문을 사용하지 않았다.

 

[ 96쪽 숫자 카드 게임 ]

 

My code

n, m = map(int, input().split())
array = [[0]*m for _ in range(n)]
first = []
result = 0
for i in range(n):
    array[i] = list(map(int, input().split()))
    array[i].sort()
    first.append(array[i][0])

result = max(first)
print(result)

 

책 속 Code

# 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) # 최종 답안 출력

• 리스트를 추가적으로 만들지 않고 현재 행의 최소값과 min_value라는 변수를 비교해서 min_value 갱신

 

[ 99쪽 1이 될 때까지 ]

 

My Code

n, k = map(int, input().split())
count = 0
while n != 1:
    if n % k == 0:
        n = n // k
        count += 1
    else:
        n -= 1
        count += 1

print(count)

 

책 속 Code

# 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)

 

[ 백준 2839 설탕 배달 ]

n = int(input())

k = n // 5
count = 0

# 5의 개수를 줄여야 하는 경우, 5&3으로 나타낼 수 없는 경우
if (n - k * 5) % 3 != 0:
    while k >= 0:
        if (n - k * 5) % 3 == 0:
            count = k + (n - k * 5) // 3
            break
        k -= 1
    if k == -1:  # 4
        count = -1
else:  # 18
    count = k + (n - k * 5) // 3

print(count)

• count = -1이 되는 부분 적절한 곳에 넣어야 함!

 

[ 백준 11047 동전 0 ]

n, k = map(int, input().split())

array = []
for _ in range(n):
    array.append(int(input()))
array.sort(reverse=True)

i = 0
count = 0

while k > 0:
    if array[i] > k:
        i += 1

    else:
        k -= array[i]
        count += 1

print(count)

• Python3로 하면 시간 초과, PyPy3로 제출해서 통과

 

[ 백준 11399 ATM ]

import sys

n = int(sys.stdin.readline().rstrip())

array = list(map(int, input().split()))
array.sort(reverse=True)

result = 0

for i in range(n):
    result += array[i]*(i+1)

print(result)