[문제풀이] 탐욕 알고리즘

문제 1: 거스름돈

백준 5585번을 풀어보자.

• 문제 난이도: 하 (Easy)
• 문제 유형: 그리디
• 추천 풀이 시간: 10분

풀이

N = int(input()) # 물건 가격
units = [500, 100, 50, 10, 5, 1] # 거스름돈 단위

def greedy(price, units):
    units.sort(reverse = True)
    change = 1000 - price
    cnt = 0
    
    for x in units:
        if change == 0:
            break
        if change >= x:
            cnt += change // x
            change %= x
    return cnt

print(greedy(N, units))

문제 2: 뒤집기

백준 1439번을 풀어보자.

• 문제 난이도: 하 (Easy)
• 문제 유형: 그리디
• 추천 풀이 시간: 20분

풀이

data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1으로 바꾸는 경우

if data[0] == '1':
    count0 += 1
else:
    count1 += 1
    
for i in range(len(data) - 1):
    if data[i] != data[i + 1]:
        if data[i + 1] == '1':
            count0 += 1
        else:
            count1 += 1
        
print(min(count0, count1)) # 두 가지 경우 중 최소를 출력

이 문제는 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우의 수를 모두 계산한 뒤, 둘 중에 최소를 구하면 된다.

• 전부 0으로 바꾸는 경우
  1. 첫 번째 원소가 1인 경우 -> +1
  2. 0 에서 1 으로 바뀔 때 -> +1
• 전부 1으로 바꾸는 경우
  1. 첫 번째 원소가 0인 경우 -> +1
  2. 1 에서 0 으로 바뀔 때 -> +1

문제 3: 등수 매기기

백준 2012번을 풀어보자.

• 문제 난이도: 하 (Easy)
• 문제 유형: 그리디
• 추천 풀이 시간: 20분

풀이

N = int(input())
expect = list()

for _ in range(N):
    expect.append(int(input()))
    
expect.sort()

result = 0
for i in range(N):
    result += abs(expect[i] - (i + 1))

print(result)

문제 4: 배

백준 1092번을 풀어보자.

• 문제 난이도: 중 (Medium)
• 문제 유형: 그리디
• 추천 풀이 시간: 35분

예를 들어, 크레인의 무게 제한이 9 8 6 이고 박스 무게가 9 9 9 7 5 라면,
처음 1분 동안 세 대의 크레인이 무게가 9 7 5 인 박스를 옮기고
추가로 2분 동안 용량이 9 인 크레인이 무게가 9 인 박스를 두 번 옮겨야 한다.
따라서 총 3분이 소요되는 것이다.

풀이

내 풀이

import sys

# 입력
N = int(input())
cranes = list(map(int, input().split()))
M = int(input())
boxes = list(map(int, input().split()))

# 내림차순 정렬
cranes.sort(reverse=True)
boxes.sort(reverse=True)

# 모든 박스를 배에 옮길 수 없는 경우
if max(boxes) > max(cranes):
    print(-1)
    sys.exit()
    
# isMoved 초기화
isMoved = list() # [박스 무게, 옮겨졌는지]
for box in boxes:
    isMoved.append([box, False])
    
# 결과 계산
result = 0 # 모든 박스를 배로 옮기는데 드는 시간의 최솟값
cnt = 0 # 옮긴 박스 수
while cnt < M:
    for crane in cranes:
        for box in isMoved:
            if crane >= box[0] and box[1] == False:
                box[1] = True
                cnt += 1
                break
    result += 1
    
print(result)

직접 입력했을 때에는 모든 테스트 케이스를 통과하지만
백준에 제출하니 시간 초과가 발생한다ㅜㅜ

강의 풀이

import sys

N = int(input()) # 크레인 수
cranes = list(map(int, input().split()))
M = int(input()) # 박스 수
boxes = list(map(int, input().split()))

if max(cranes) < max(boxes):
    print(-1)
    sys.exit()
    
positions = [0] * N # 각 크레인이 현재 옮겨야 하는 박스의 번호 (0부터 시작)
isMoved = [False] * M # 각 박스를 옮겼는지 여부

cranes.sort(reverse = True)
boxes.sort(reverse = True)

result = 0 # 모든 박스를 배로 옮기는데 드는 시간의 최솟값
cnt = 0 # 옮긴 박스 수

while True:
    if cnt == len(boxes): # 박스를 다 옮겼다면 종료
        break
    for i in range(N):
        while positions[i] < len(boxes):
            # 아직 안 옮긴 박스 중에서 옮길 수 있는 박스를 만날 때까지 반복
            if not isMoved[positions[i]] and cranes[i] >= boxes[positions[i]]:
                isMoved[positions[i]] = True
                positions[i] += 1
                cnt += 1
                break
            positions[i] += 1
    result += 1

print(result)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기