★Greedy Intermediate I - 20 Solved★

🧍‍♂️ greedy 중급문제는 전형적인 greedy 대표 예제 모음이라고 생각하면 쉽다! greedy 유형은 주어진 상황에서 다양한 선택지가 있을 때 당장의 최적의 선택지를 구한 결과를 연속할 때 그 결과가 곧 최적의 결과가 된다는 내용이다. 이 때 중요한 건, 나올 수 있는 모든 상황을 정해 놓고, 그 상황에서 최적의 상황을 연속해서 구한 상황의 결과 모음이 곧 전체의 최적 상황이어야 한다는 전제가 깔려 있다.

---

★ 6752 Time on task ★

 

T = int(input()) 
C = int(input()) 

times = [int(input()) for _ in range(C)]
n = 0

times.sort()

for time in times:
    T -= time
    if T < 0:
        break
    n += 1

print(n)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) chore를 선택해 한 개의 chore를 처음부터 끝까지 끝내는 상황

: 종합 상황) 선택한 chore를 모두 끝내기 / 최적의 종합 상황) 최대 개수의 chore를 모두 끝내기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 가장 시간이 적게 걸리는 chore부터 골라서 진행(시간이 초과되면 break)

---

★ 16435 스네이크버드 ★

 

N,L = map(int, input().split())

h = list(map(int, input().split()))

h.sort()

for each_h in h:
    if each_h > L:
        break

    L += 1

print(L)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) snake 길이보다 작거나 같은 과일이 있으면 먹고 snake 길이가 늘어나는 상황

: 종합 상황) 먹을 수 있는 과일을 모두 먹음 / 최적의 종합 상황) 먹으면서 늘어날 수 있는 snake의 최대 길이

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 과일 높이를 정렬한 다음, 작은 높이부터 차례대로 먹으면서 1씩 증가하면서 최대한 길이 늘리기 (못 먹는 과일이 그 다음 있으면 break)

---

★ 1026 보물 ★

 

input()
print(sum([x*y for x,y in zip(sorted(map(int,input().split()),reverse=True),sorted(map(int,input().split())))]))

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) A[i] * B[i]

: 종합 상황) 각 A[i]*B[i]의 모든 합인 S 구하기 / 최적의 종합 상황) S 최솟값 구하기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 먼저 A를 증가 / B를 감소 순으로 정렬한 뒤, A의 최댓값 x B의 최솟값 + A의 두번째 큰 값 x B의 그 다음 최솟값... 순서로 더하기

: 보충설명) B가 고정되어 있는 상태에서 B의 최댓값부터 보자면, S를 최솟값으로 만들려면 greedy하게 일단 A의 최솟값으로 곱해주어야 한다. 가장 큰 수가 곱해지는 수는 최솟값이어야 S가 최소. (어차피 모두 A와 B 모두가 선택해서 곱해지는 상황에서)

+) zip 활용

---

★ 1789 수들의 합 ★

 

print(int(((8*int(input())+1)**(1/2)-1)/2))

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 앞서 사용하지 않은 자연수를 1개 정해 더하기

: 종합 상황) 서로 다른 자연수를 모두 더해 S로 만들기 / 최적의 종합 상황) 서로 다른 자연수의 개수 N개의 최댓값 구하기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 더해지는 자연수의 개수가 최대이려면 최대한 작은 자연수인 1부터 2, 3, 4 순으로 최대한 더해 개수를 최대화한다. 그 다음 남은 자연수가 있다면 기존에 더한 자연수와 더해서 제일 큰 또 다른 자연수 1개로 합치면 서로 다른 자연수 개수 최댓값을 구할 수 있다. (1부터 안더하고 예를 들어 10을 더한다면 10에 1이 들어가므로 greedy 성립)

: 보충설명) 예를 들어 S가 198이라면 1부터 19까지 쭉 더한 결과는 190이고 8이 남는다. 남는 8은 더한 자연수 최댓값 19와 합쳐 27을 만들면 됨. 즉 최대 개수는 19. 따라서 1부터 x까지 더한 결과가 S보다 크거나 같다면, x의 최댓값이 정답. (아래 식 확인)

 

🧍‍♂️

$ \frac{n(n+1)}{2} \leq S < \frac{(n+1)(n+2)}{2}$

 

: 위 식을 만족하는 n 구하기. n에 대해 부등식 풀어서 int() 함수 결과로 구하면 끝

: 부등식을 풀면 아래와 같다.

 

$n\leq \frac{\sqrt{8S+1}-1}{2}$

---

★ 1758 알바생 강호 ★

 

import sys
def input(): return sys.stdin.readline().rstrip()

total = int(input())
max_tip = 0
think = [int(input()) for _ in range(total)]

think.sort(reverse=True)

for i in range(total):
    tip = think[i] - (i+1) + 1
    if tip > 0:
        max_tip += tip
    else:
        break

print(max_tip)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 정해진 사람별로 등수를 적절히 정하기

: 종합 상황) 사람별 정해진 등수에 맞게 tip 부여해서 최종 tip 합계 구하기 / 최적의 종합 상황) 최댓값 tip 구하기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 각 사람별로 [생각한 tip - 등수 + 1]의 합이 최댓값이 되어야 한다. 여기서 생각한 tip과 1은 정해져 있으므로 생각한 tip이 많은 사람일수록 등수를 최소화해야 한다.

---

★ 11047 동전 0 ★

 

import sys
input=sys.stdin.readline
N,K=map(int, input().split())
a=0
l=[i for i in [int(input()) for _ in range(N)]if i<=K]
for A in l[::-1]:
    a+=(K//A)
    K%=A
    if K==0:break
print(a)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 동전의 종류를 정하기

: 종합 상황) K원을 만들기 / 최적의 종합 상황) K원을 만들기 위한 동전의 개수 최소화

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 동전의 종류 가치가 높은 것부터 먼저 카운트 (이 때 모든 동전의 종류 가치: 큰 가치가 작은 가치의 배수이므로 당장 큰 종류를 선택한 상황이 greedy로 성립)

---

★ 15761 Lemonade Line ★

 

N = int(input())
ws = list(map(int, input().split()))
ws.sort(reverse=True)
front_num = 0
print(ws)
for i in range(N):
    if ws[i] >= front_num:
        front_num += 1

print(front_num)
#-----------------------------
N = int(input())
ws = list(map(int, input().split()))
ws.sort(reverse=True)
front_num = 0
for i in range(N):
    if ws[i]<front_num:
        break
    front_num += 1

print(front_num)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) cow wi가 갈 지 말 지 결정

: 종합 상황) line에 서는 cow들 / 최적의 종합 상황) line에 선 cow의 최소 개수

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 wi가 높은 cow부터 먼저 line up

: 보충설명) 능력이 큰 순서가 먼저 오게끔 해서, 능력이 작은 소가 큰 소에 비해 먼저 떠날 확률이 높기 때문 (능력이 작은 소일수록 앞에 선 소의 개수가 정해져 있다면 떠날 확률이 무조건 높기 때문에)

+ 한 번 소가 떠난다면 그 뒤의 소는 wi가 작아지므로 무조건 앞에 선 소의 개수보다 작기 때문에 떠남 → break 설정

---

★ 2839 설탕 배달 ★

 

N=int(input())
y=0
for i in range(N//5,-1,-1):
    if (N-5*i)%3==0:
        y+=1
        print(i+(N-5*i)//3)
        break
if y==0:print(-1)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 설탕 배달할 때 3kg / 5kg 봉지 중 1개 선택해서 배달하기

: 종합 상황) 정확히 Nkg 배달 / 최적의 종합 상황) 최소 봉지수로 배달하기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 봉지수가 최솟값이 되어야 한다. 먼저 5kg을 최대 수로 배달할 수 있는 지 5kg으로 나눈 몫부터 1까지 차례대로 감소하며 5kg을 나눈 나머지는 3kg로 나눌 수 있는 지 확인 (확인되면 break)

---

★ 14916 거스름돈 ★

 

n=int(input())
flag=False
for i in range(n//5,-1,-1):
    if (n-i*5)%2==0:
        flag=True
        print(i+(n-i*5)//2)
        break
if not flag: print(-1)

 

🧍‍♂️ 위 [2839 설탕배달] 문제와 완전히 똑같은 문제. 2원보다 5원이 우선시되어야 봉지 개수가 최소이므로 5원 먼저 알아보는 greedy. 설명 생략

---

★ 1246 온라인 판매 ★

 

import sys
def input(): return sys.stdin.readline().rstrip()

N,M = map(int, input().split())
num=M
Ps = [int(input()) for _ in range(M)]
Ps.sort()

sug_price,max_profit=0,0
for price in Ps:
    n=min(num,N)
    if n*price > max_profit:
        max_profit = n*price
        sug_price = price
    num-=1
print(sug_price, max_profit)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 각 고객별 Pi가 경래가 책정한 A 가격보다 크거나 같다면 구매 

: 종합 상황) 고객 일부는 사고, 일부는 사지 않아서 수익 내기 / 최적의 종합 상황) 종합 최대 수익의 가장 낮은 A 가격

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 수익은 최대 / 가격 A는 최소. Pi 정렬하고 낮은 Pi부터 Pi x (min(달걀개수, 책정가격에 따른 구매 가능인원수))의 최댓값 update

: 주어진 Pi만(*greedy) 확인 → 달걀 개수와 구매 가능인원수 정해진 상태에서 Pi가 무조건 최대이므로

---

★ 11399 ATM ★

 

import sys
input=sys.stdin.readline
input()
P=list(map(int,input().split()))
P.sort()
ans,a=0,0
for t in P:
    a+=t
    ans+=a
print(ans)

 

🍇 greedy 관점 분석

: 개별 상황) ATM 인출

: 종합 상황) 모두 인출하고 난 뒤의 최종 시간 / 최적의 종합 상황) 최종 시간 최솟값

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 빨리 인출할 수 있는 사람을 먼저(Pi값이 작은 순) 인출하게끔 해야 최종 시간 최소

---

★ 20044 Project Teams ★

 

import sys
input=sys.stdin.readline

n = int(input())
s = sorted(list(map(int, input().split())))

w = s[0] + s[-1]
l = len(s)

for i in range(l//2):
    w = min(w, s[i] + s[l-1-i])

print(w)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 2인 1조로 팀에 들어갈 코딩 역량 2개 선택

: 종합 상황) 모든 팀의 각각의 팀 코딩 역량 / 최적의 종합 상황) 각각의 팀 코딩 역량 중 최솟값

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 팀 코딩 역량이 최대한 팀별로 일정하게 유지하기 위해서 정렬해 왼쪽과 오른쪽에서부터 각각 시작해 최솟값과 최댓값의 합으로 묶어 팀을 만들어 나간다. (비둘기 집의 원리에 의해, 이에 반하게 팀을 구성하면 적어도 한 팀은 다른 팀에 비해 두 명 모두 팀의 역량이 적게 산출된다.)

 

※ 즉, 위 문제의 $S_m$값이 최대가 되기 위해선 최대한 팀끼리 합의 차이가 안나도록 공평하게 양쪽에서 가운데로 진행하며 합을 구해야 함

(직관적 증명이 다소 가미됨..!)

---

★ 1448 삼각형 만들기 ★

 

import sys
input = sys.stdin.readline

N = int(input())
y = -1
straws = [int(input()) for i in range(N)]
straws.sort(reverse=True)

for i in range(N-2):
    if straws[i] < straws[i+1] + straws[i+2]:
        y = straws[i]+straws[i+1]+straws[i+2]
        break
print(y)

 

🧍‍♂️ 삼각형의 결정 조건: 제일 긴 변 < (나머지 두 변의 합)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 삼각형으로 만들 세 개의 변 선택

: 종합 상황) 선택한 세 변이 삼각형이 되는 지 확인 / 최적의 종합 상황) 만들어진 삼각형 세 변의 합 최댓값

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 먼저 정렬(reverse=True)한 뒤(greedy), 최댓값부터 그 다음 두 개의 변의 합이 더 큰 지 확인 (이 때, 더 크지 않다고 결론이 났으면 그 이후의 수는 더 작으므로 당연히 삼각형의 결정조건을 만족시킬수 없으므로 위 for문 i index 바로 이동: greedy)

∴ 위 두 greedy한 상황을 설정해 메모리, 시간 초과 문제를 해결할 수 있다! (greedy의 장점)

---

★ 13305 주유소 ★

 

 

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 각 구간 거리별 선택할 주유소

: 종합 상황) 목적지까지 도착 후 지불한 금액 / 최적의 종합 상황) 지불 금액이 최소

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 어차피 구간 거리는 모두 mulsum으로 곱해지므로, 우리가 바꿀 수 있는 건 주유소 가격. 종합 금액이 최소일려면 현재 구간까지의 주유소 가격을 최솟값으로 update하면서 계속 가격을 구해나감

import sys
input=sys.stdin.readline

N = int(input())

t=0

dist=list(map(int, input().split()))
price=list(map(int, input().split()))

cur_min_price=price[0]
price=price[:-1]

for i in range(N-1):   
    if price[i]<cur_min_price:
        cur_min_price=price[i]
        t+=price[i]*dist[i]
    else:t+=cur_min_price*dist[i]

print(t)

---

★ 1343 폴리오미노 ★

 

import sys
input = sys.stdin.readline

board = list(input())
length = len(board)
Xs,ans=[],[]
cnt = 0
possible = True

for i in range(length):
    if board[i] == 'X':
        cnt += 1
    else:
        Xs.append(cnt)
        cnt = 0
    if i == (length-1) and cnt != 0:
        Xs.append(cnt)

for i in range(len(Xs)):
    if Xs[i]%2 == 1:
        possible = False
        print(-1)
        break
    if (Xs[i]//4) != 0:
        ans.append('AAAA'*(Xs[i]//4))
    if (Xs[i]%4) != 0:
        ans.append('BB'*((Xs[i]%4)//2))
    if i != (len(Xs)-1):
        ans.append('.')

if possible: print(*ans,sep='')

 

🧍‍♂️ 사전순으로 가장 앞서는 답을 출력해야 하므로 당장의 선택지 (1) AAAA (2) BB 중에서 (1)을 무조건 골라야 한다! 다만, 이 때 보드판을 덮을 때 몇가지 생각할 상황만 고려해서 코딩해주면 끝!

 

🧍‍♂️AAAA로 덮을 때 고려 상황

(1) 먼저 X묶음내의 X개수를 쭉 알아야 한다. (.을 만나면 그 전까지 X 묶음이 생성)

(2) X개수가 들어간 Xs를 list로 돌리면서

→ X의 개수가 홀수면 보드판을 AAAA, BB로 덮을 수 없으므로 -1 출력. 바로 break

→ X의 개수가 짝수일 경우 4로 나눈 몫 개수만큼 AAAA로 먼저 덮고(greedy), 4로 나눈 나머지가 2일 경우 BB를 그 다음 덮어준다.

(3) 한번 X묶음을 모두 덮고 나면 .으로 마무리

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 각 문자를 A로 바꾸거나 B로 바꾸거나 그대로 놔두거나

: 종합 상황) 최종적으로 바뀐 보드판 / 최적의 종합 상황) 바뀐 보드판이 사전순으로 제일 앞서는 경우 출력

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 최대한 AAAA로 덮기(X가 홀수이면 불가능하므로 -1, 짝수라면 4로 나눈 몫은 A로 4로 나눈 나머지(즉 2개)는 B로 덮기

 

🧍‍♂️ ans list에 계속 결과를 append하면서 최종 결과 출력!

 

++ 추가로 python replace 함수를 이용하면 한번에 풀 수 있다. XXXX먼저 AAAA로 깔고 남은 XX를 BB로 깐다. 그래도 X가 남으면 -1 출력

board = input().replace('XXXX', 'AAAA').replace('XX', 'BB')

print(-1 if 'X' in board else board)

---

★ 12845 모두의 마블 ★

 

import sys
input=sys.stdin.readline

n=int(input())
L=list(map(int,input().split()))
print(max(L)*(n-1)+sum(L)-max(L))

 

🧍‍♂️ 인접한 카드 쌍의 개수는 정해져 있다. 최댓값을 구한 후, 최댓값을 기준으로 양옆으로 쌍으로 뻗어나가면서 매번 더하는 쌍 내부에 최댓값이 무조건 적용되게 한다. (greedy)

 

: 정해진 인접쌍 개수 내에서 각각의 쌍에 최댓값이 들어가게 하는 greedy한 상황 선택, 최댓값 제외 모든 카드의 숫자는 각 쌍에서 한 번씩 더해지므로 최댓값 x (쌍의 개수) + (최댓값 제외 모든 카드 숫자 합)

---

★ 20310 타노스 ★

 

S=input()
zero=S.count('0')//2
one=S.count('1')//2
ans=[]
zero_cnt,one_cnt=0,0
for n in S:
    if n == '0':
        if zero_cnt < zero:
            ans.append(0)
            zero_cnt+=1
    else:
        if one_cnt >= one:
            ans.append(1)
        else:
            one_cnt+=1
print(*ans,sep='')

 

🧍‍♂️0과 1의 갯수는 정해져 있는 상태에서 가장 사전순으로 앞서는 숫자를 찾으려면 0은 오른쪽부터 지워야 하고, 1은 왼쪽부터 지워야 한다.

 

: 정해진 갯수 상황 내에서 최적의 결과를 내기 위해 왼쪽부터 0은 놔두고 1은 지우는 greedy한 상황! 문제만 바로 읽으면 바로 풀림.

---

★ 15904 UCPC는 무엇의 약자일까? ★

 

i=0
for s in input():
    if s=='U' and i==0:i+=1
    if s=='C' and i==1:i+=1
    if s=='P' and i==2:i+=1
    if s=='C' and i==3:
        i+=1
        break
print('I love UCPC'if i==4 else'I hate UCPC')

 

🍇 greedy 관점 분석

: 개별 상황) 매 문자를 확인하는 상황

: 종합 상황) 문자를 확인해서 UCPC 확인할 수 있는 지 체크

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 U → C → P → C 순서로 확인(다 구하면 break)

---

★ 2217 로프 ★

 

import sys
input=sys.stdin.readline
N=int(input())
ropes=[int(input()) for _ in range(N)]
ropes.sort()
i,ans=0,0
for rope in ropes:
    ans=max(ans,rope*(N-i))
    i+=1
print(ans)

 

🍇 greedy 관점 분석

: 개별 상황) 주어진 로프의 개수 x에서 들어올린 최대 중량

: 종합 상황) 주어진 로프의 여러 개수에의 최대 중량 모음  / 최적의 종합 상황) 그 중 최댓값

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 (먼저 ropes 오름차순 정렬) ex) 1개일 경우 (가장 큰 rope * 1) / 2개일 경우 가장 큰 rope과 그 다음 큰 rope 사용 가능하고 그 중 최솟값인 (그 다음 큰 rope * 2) /... 전체 N개일 경우 (최솟값 rope * N) → 각각의 모든 경우중 최댓값 구하기

---

★ 29198 이번에는 C번이 문자열 ★

 

import sys
input=sys.stdin.readline
N,M,K=map(int,input().split())
print(''.join(sorted(''.join(sorted([''.join(sorted(input().strip())) for _ in range(N)])[:K]))))

 

★ greedy 3번 적용 → 정렬 3번 적용 문제 / 2023 KSA Automata Summer Contest 기출

 

🍇 greedy 관점 분석

: 개별 상황) 문자열 K개 선택한 뒤 만들어진 KxM개의 문자중 1개씩 선택

: 종합 상황) 길이 KxM의 문자열 T 만들기 / 최적의 종합 상황) 사전 순으로 가장 먼저 오는 문자열 T 만들기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 (1) 먼저 정렬된 문자열 S1 ~ Sn 중, 정렬해 사전 순 가장 앞에 오는 문자열 K개 선택 (2) 총 KxM개의 모든 문자를 정렬(사전순 정렬)

 

: 여기서 중요한 건, 문자를 서로 섞어 재배치할 수 있음. 따라서 (1) 문자열 내부 먼저 정렬 / (2) K개 선택을 위해 문자열을 정렬 / (3) 만들어진 KxM개의 문자를 정렬 ▶ 우선적으로 맨 앞자리가 뒷자리보다 사전순으로 중요하기 때문에 greedy원리 적용

---