이코테 강의 몰아보기 | 2-2. 그리디 & 구현

[3] 실전 문제

1. 그리디

#3-1. 큰 수의 법칙(Page92)

아이디어 : 전형적인 그리디 알고리즘 문제로, 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다.

연속으로 더할 수 있는 횟수는 최대 K번이므로 '가장 큰 수를 K번 더하고 두 번 째로 큰 수를 한 더 더하는 연산'을 반복

#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 #더할 때마다 1씩 빼기
    if m == 0: #m이 0이라면 반복문 탈출
        break
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 #더할 때마다 1씩 빼기

print(result)

 

#3-2. 숫자 카드 게임(Page96)

아이디어 : 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 문제

# N, 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(result, min_value)
    
print(result)

 

#3-3. 문자열 뒤집기(Page313)

아이디어 : 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 계산한다.

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]:
        #다음 수에서 1로 바뀌는 경우
        if data[i+1] == '1':
            count0 += 1
        #다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0,count1))

 

#3-4. 만들 수 없는 금액(Page314)

아이디어 : 정렬을 이용한 그리디 알고리즘으로 해결할 수 있는 문제이다.  1원부터 N원까지 증가시키며 동전을 가지고 만들 수 있는지 확인한다.

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    #만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x

#만들 수 없는 금액 출력
print(target)

 

 

#3-5. 볼링공 고르기(Page315)

아이디어 : 무게마다 볼링공이 몇 개 있는지를 계산한다.

 A가 특정 무게를 선택하고 이어서 B가 볼링공을 선택하는 경우를 차례대로 계산하여 문제를 해결한다.

이미 계산했던 경우(조합)는 제외한다.

n, m = map(int, input().split())
data = list(map(int, input().split()))

#1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11
for x in data:
    #각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1
    
result = 0
#1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m+1):
    n -= array[i] #무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i] * n #B가 선택하는 경우의 수와 곱하기

print(result)

 

#3-6. 무지의 먹방 라이브(Page316)

아이디어 : 그리디(탐욕적)접근 방식으로 해결한다. 

모든 음식을 시간을 기준으로 정렬한 뒤에, 시간이 적게 걸리는 음식부터 제거해 나가는 방식을 이용하면 된다.

이를 위해 우선순위 큐(최소 힙)을 이용하여 구현한다.

import heapq

def solution(food_times, k):
    #전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1
    
    #시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i+1))
    sum_value = 0 #먹기 위해 사용한 시간
    previous = 0 #직전에 다 먹은 음식 시간
    length = len(food_times) #남은 음식의 개수
    
    #sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 K비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 #다 먹은 음식 제외
        previous = now #이전 음식 시간 재설정
    #남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x:x[1]) #음식의 번호 기준으로 정렬
    return result[(k- sum_value) % length][1]
 
food_times = [3,1,2]
k = 5
 
print(solution(food_times,k))