★Greedy Upper-Intermediate I - 8 Solved()★

🦒 문제 자체의 최적의 솔루션

---

★ 11497 통나무 건너뛰기 ★

 

🦒 문제를 이해하고 idea를 생각하는 게 중요!

 

🦒 인접한 두 통나무 높이 차의 최댓값을 최소화하는 문제

① 즉, 최소화하기 위해서는 인접한 두 통나무간의 높이 차가 최소화되어야 한다

② 서로간의 높이 차를 최소화하려면, 가장 큰 통나무부터 순서대로 $h_1, h_2, h_3, h_4, .... h_n$으로 정렬한 뒤, $h_1$을 정중앙에, 그 다음 $h_2, h_3$를 양옆에, $h_4, h_5$를 그 다음 양 옆에 차례대로 배치하면, 서로 간의 높이 차를 최소화할 수 있다.

 

🦒 greedy의 생명은 시간 단축! 매우 많은 풀이를 보며 시간 단축을 문제의 특성에 맞게 code로 고쳐가며 진행해보자

 

- 352ms -

 

① 위 그림에 맞게 제일 높은 통나무를 가운데 중심, 그 양 옆에 그 다음 높은 통나무 2개, 이런 순서로 양 옆으로 뻗어가며 만들어보기

→ slicing기법 사용

→ 먼저 정렬 후 step 2씩 밟으며 제일 높은 통나무까지 정렬한 뒤, 다시 처음 위치를 향해 step 2씩 밟으며 나머지 통나무 정렬

(개수가 홀/짝 여부에 따라 나누어 정렬)

 

② 이제 다 정렬했다면, 각 인접한 통나무 간의 높이 차 abs() 사용해 빈 list에 모든 element 넣은 뒤, 최댓값 출력

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    Lis = list(map(int, input().split()))
    Lis.sort()
    height_diff = []

    if N%2 == 0:
        heights = Lis[::2]+Lis[::-2]
    else:
        heights = Lis[::2]+Lis[-2::-2]
    
    for i in range(len(heights)):
        if i == len(heights) - 1:
            i = -1    
        height_diff.append(max(abs(heights[i]-heights[i+1]), abs(heights[i] - heights[i-1])))
    
    print(max(height_diff)) #최종 372ms - 효율적 code 더 찾아보기

 

- 236ms -

 

※ 별도의 list만들어 해당 list의 최댓값을 구하는 것 보다는, 지속적으로 최댓값을 update해서 변수값을 출력하는게 더 빠름

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    Lis = list(map(int, input().split()))
    Lis.sort()

    if N%2 == 0:
        heights = Lis[::2]+Lis[::-2]
    else:
        heights = Lis[::2]+Lis[-2::-2]

    ans = abs(heights[0]-heights[-1])

    for i in range(N):
        ans = max(ans, abs(heights[i]-heights[i-1]))
    print(ans)

 

- 148ms -

 

※ 위 그림의 인접한 두 통나무의 차이는 결과적으로 slicing 진행 없이, 현재 통나무와 두 step 떨어진 통나무와의 높이 차이이므로  정렬 후 단순히 index로 2 떨어진 만큼의 차이를 구하면 된다. 여기서 정렬이 이미 진행되었으므로 abs() 함수 사용 없이 단순히 큰 높이에서 작은 높이를 빼면 된다.

※ 위 예시) 맨 마지막 두 통나무는 인접한 통나무 차를 비교해봤자 이미 앞에서 비교대상에 포함되거나, (예) 5와 6은 앞서 비교 대상인 4와 6보다 클 수가 없으므로 배제. 즉 1부터 4까지만, 1부터 n-2까지만 step 2 간격 diff 최댓값 update

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    Lis = sorted(list(map(int, input().split())))
    print(max([Lis[i+2]-Lis[i] for i in range(N-2)]))

---

★ 9440 숫자 더하기 ★

 

import sys
input=sys.stdin.readline
import math

while 1:
    l=list(map(int,input().split()))
    
    N=l[0]
    
    if N==0:break

    numbers=l[1:]
    numbers.sort()

    without_zeros=[i for i in numbers if i!=0]

    ans = 0

    for i in range(N):
        digits=10**(math.ceil((N-i)/2)-1)

        if i==0 or i==1:
            n=without_zeros[0]
            ans+=digits*n
            without_zeros=without_zeros[1:]
            numbers.remove(n)

        else:
            ans+=digits*numbers[0]
            numbers=numbers[1:]

    print(ans)

 

🦒 greedy하게, 가장 작은 수부터 가장 큰 자리수부터 차례대로 배열한 다음, 더하면 끝

 

🦒 단, 두 수 각각 맨 앞자리에 0이 올 수 없음

→ 전체 N개의 숫자가 있으므로, 이를 range() 문으로 돌려, 첫 숫자 & 두 번째 숫자의 경우 0을 제외한 최소를 구하고, 이후는 그저 최솟값을 자리수와 곱한 값을 total 변수에 계속 add up

→ 이 때, 두 수의 자리수가 똑같은 숫자들의 경우, 서로 숫자 자리가 바뀌어도 상관 없다. 그저 서로 더한 다음, 해당 10의 자리수를 곱한 값을 add up

 

※ 정리)

① without_zeros에서 맨 앞의 두 개 숫자 선택 - digits에 곱

② 그 다음부터는 numbers에서 맨 앞의 숫자 계속 선택 - digits에 곱

 

(math.ceil(N-i/2)-1이 10의 자릿수)

 

※ 추가) str()에 숫자 추가 → 한 번의 int()로 자릿수 계산 없이 숫자 형성 ※

while True:
    n = input()
    if n == '0': break
    li = sorted(n.split()[1:])
    num1, num2 = str(), str()
    for i in range(len(li)):
        if li[i] != '0':
            num1, num2 = li[i], li[i + 1]
            li = li[:i] + li[i + 2:]
            break
    for i in range(0, len(li), 2):
        num1 += li[i]
        if i < len(li) - 1:
            num2 += li[i + 1]

    print(int(num1) + int(num2))

---

★ 1541 잃어버린 괄호 ★

 

import sys
input=sys.stdin.readline


def split_and_calculate(exp,sign):
    l = list(exp.split(sign))
    ans = int(l[0])

    for number in l[1:]:
        if sign == '+':
            ans += int(number)
        else:
            ans -= int(number)
    return ans

exp=input().rstrip()

if '+' not in exp: #only consists of '-'
    print(split_and_calculate(exp,'-'))
elif '-' not in exp: #only consists of '+'
    print(split_and_calculate(exp,'+'))
else: #'+' and '-'
    l = list(exp.split('-'))
    if '+' in l[0]:
        ans = split_and_calculate(l[0],'+')
    else:
        ans = int(l[0])

    for small_exp in l[1:]:
        if '+' in small_exp:
            ans -= split_and_calculate(small_exp,'+')
        else:
            ans -= int(small_exp)
    print(ans)

 

🦒 문제 상황은 크게 세 가지로 나눌 수 있다.

① +로만 구성된 식

② -로만 구성된 식

③ +와 -가 같이 존재하는 식

 

🦒 ①② + 또는 -로만 이루어진 식은 결과가 최소가 되게 하기 위해서는 그저 괄호의 사용 없이 그대로 연산해주면 된다.

→ + 로만 이루어진 식은 괄호를 쳐도 어차피 수가 계속 더해지므로 결과 변동 x

→ -로만 이루어진 식은 괄호를 칠 경우 -가 -와 만나 +가 되어 오히려 더 커지므로 괄호 사용 없이 그대로 연산해야 최솟값이 나온다.

 

🦒 ③ +와 -가 같이 존재하는 경우, 최대한 +있는 식들을 다 더해 앞에 -가 있을 때 + 기호들의 결과를 한 번에 빼줘야 최솟값이 나온다.

→ 먼저 -를 기준으로 split() 한 다음, + 결과들이 모인 element의 결과가 모이면 첫 번째부터 시작해서 쭉 빼주면 된다.

---

★ 1931 회의실 배정 ★

 

import sys
input=sys.stdin.readline

N=int(input())
meetings=[]

for _ in range(N):
    flag=True
    s,e=map(int,input().split())
    meetings.append((s,e))
meetings.sort(key=lambda a: (a[1],a[0]))

ans = 1
cur = meetings[0][1]
for meeting in meetings[1:]:

    if cur <= meeting[0]:
        ans += 1
        cur = meeting[1]

print(ans)

 

🦒 어려울수록 최대한 간단하게 생각하자. 내가 회의를 현재 하고 있거나 / 하지 않거나 둘 중 하나인데, 그 어떤 상황에서라도 일단 회의를 잡아야 하는 greedy한 상황에서, 회의의 개수를 최대화할려면 내가 잡을 회의가 빨리 끝나야 한다.

 

🦒 그렇다면, 당장 빨리 끝나는 회의를 잡는 것이 곧 최적의 해가 되는 지 greedy의 정당성을 따져봐야 하는데,

 

내가 회의를 잡을 때 어떤 한 회의를 기준으로 무조건 아래와 같이 9가지의 상황으로 나눌 수 있다.

🦒 내가 그 다음 회의를 고를 때, 한 개의 회의를 기준으로 시작과 끝이 각각 크고 작고 같은 지 3 x 3 결과 9개의 경우의 수가 있다.

★ greedy를 증명하려면 무조건 모든 경우의 수를 따지고 greedy하게 골라야 한다 ★ 이 때 시작과 끝이 모두 같은 건 중복되므로 제외. 모든 상황에서 총 8개의 후보 회의를 마주하게 된다.

 

① 먼저, 기준회의보다 늦게 끝나는 (2) / (4) / (8)은 제외. 기준 회의 뒤에 추가 회의가 있을 수 있어서 카운트가 더 될 가능성이 있기 때문.

② 기준회의와 (5) / (6)도 제외. (1) (3) (7) 회의 뒤에 추가 회의가 있을 수 있으므로 역시 카운트가 더 될 수 있어서 제외

 

🦒 따라서, 우리는 회의의 끝나는 시간을 정렬해 가장 먼저 끝나는 (1) (3) (7) 회의를 무조건 선택해야 함을 알 수 있다. 이 때, (1) (3) (7) 세 개 회의의 시작 시간이 모두 다른데, 애초에 앞에 회의를 모두 선택했고 그 다음 회의를 고르는 상황이라 시작 시간 순서는 무방하다. 끝나는 시간이 무조건 빠르기만 하면 되는 것이다. (greedy)

 

🦒 (+예외) 만약 (9, 9) (1, 9)가 선택되었다면 (1,9)가 선택되지 않으므로 시작시간 = 끝나는 시간인 회의를 추가로 고려해 끝나는 시간을 정렬한 다음, 시작 시간을 정렬하자. 그래서 베스트는 회의 (1)

 

🦒 코드

① lambda로 한번에 끝나는 시간 정렬 → 시작 시간 정렬 lambda a: (a[1], a[0])

② 첫번째 meeting은 카운트 한 상태에서 현재 meeting의 끝나는 시간을 cur 변수로 두고 그 다음 meeting부터 meeting의 시작 시간이 끝나는 시간보다 크거나 같은 지 계속 확인하면서 cur 변수에 다음 올 meeting의 끝나는 시간을 update하며 meeting 개수 update

---

★ 20117 호반우 상인의 이상한 품질 계산법 ★

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 각 호반우별로 묶을 지 / 또는 개별로 진행할 지 선택

: 종합 상황) 묶음 또는 개별 호반우의 품질을 모두 더하기 / 최적의 종합 상황) 품질 최댓값 꺼내기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 정렬한 뒤 (1번째 큰 것, 1번째 작은 것) (2번째 큰 것, 2번째 작은 것), 이런 순으로 (i번째 큰 것, i번째 작은 것) / 홀수 개수면 중앙 호반우 개별 1개

 

: 가장 작은 수가 최댓값으로 당장 바뀌고, 이후 그 다음 최댓값이 그 다음 최솟값으로 바뀌면서 진행되어야 최댓값이 나온다. 최댓값을 현재의 최솟값으로 바꿔주는게 최선의 상황. 그게 아니라 여러 개로 묶는다면 최대 / 최소가 아닌 수가 서로 바뀔 경우 그 사이의 차이는 최댓값-최솟값 차이보다 무조건 작기 때문에 최선의 상황이 아님

---

★ 1946 신입 사원 ★

 

import sys
input=sys.stdin.readline
for _ in range(int(input())):
    N=int(input())
    l=[]
    for _ in range(N):
        a,b=map(int,input().split())
        l.append((a,b))
    l.sort()
    ans,cur=N,l[0][1]
    for pair in l[1:]:
        if pair[1]>cur:
            N-=1
        else:
            cur=pair[1]

    print(N)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 각 사원 성적을 보면서 두 영역 모두 순위가 떨어지는 사원이면 제외

: 종합 상황) 모두 제외하고 남은 신입사원들 / 최적의 종합 상황) 최대로 선발할 수 있는 남은 신입사원들 명수

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 먼저 서류심사 성적 순으로 1위부터 정렬한 뒤 면접 성적만 이용해서 앞선 신입사원 최고순위보다도 못한 순위라면 1명씩 제외: 즉 cur 변수로 현재 최고 순위를 update해가며 현재 최고순위보다 못한 순위면 제외. 더 나은 순위면 cur update

---

★ 1449 수리공 항승 ★

 

import sys
input=sys.stdin.readline
cnt=0
N,L=map(int,input().split())
spots=sorted(list(map(int,input().split())))
ans,start=1,spots[0]-0.5

for spot in spots:
    if (spot+0.5-start)>L:
        start=spot-0.5
        ans+=1
print(ans)

 

🧍‍♂️ greedy 관점 분석

: 개별 상황) 물이 새는 곳을 테이프로 붙이기

: 종합 상황) 물이 새는 모든 곳을 각각 테이프로 붙임 / 최적의 종합 상황) 붙인 테이프 개수 최솟값

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 매 leak 끝부분과 현 start 지점 사이의 값이 테이프 길이 L을 넘는 지 매번 확인하고 넘으면 일단 테이프 1개 필요하므로 1 카운트 / 어차피 테이프는 정수 +- 0.5 지점에 시작하거나 멈추므로 현 leak 시작부분을 start로 설정

 

★ 심화 greedy: 일단 테이프가 더 필요한 상황이면 바로 +1로 누적해 나감 (어려운 다양한 상황 고려 없이 어쩔 수 없는 상황 1개만 만들어서 그대로 카운트)

---

★ 30022 행사 준비 ★

 

🧍‍♂️ 각 물건이 A 상점 또는 B 상점에 있는데 두 상점 중 한 곳을 선택. 이 때 각 상점별 사야하는 품목의 개수는 정해져 있으므로, greedy의 핵심은 일단 상점 간의 가격 차가 큰 곳부터 점령 → 특정 상점의 품목 개수가 다다르면 그 때는 다른 상점 점령

 

import sys
input=sys.stdin.readline

N,A,B=map(int,input().split())
total=0
diff=[]
l1,l2=[],[]
for _ in range(N):
    a,b=map(int,input().split())
    l1.append(a)
    l2.append(b)
combined = [(l1[i], l2[i]) for i in range(N)]
combined.sort(key=lambda x: abs(x[0] - x[1]),reverse=True)
for x in combined:
    if (x[0]-x[1])>0:
        if B > 0:
            B-=1
            total+=x[1]
        else:
            A-=1
            total+=x[0]
    else:
        if A > 0:
            A-=1
            total+=x[0]
        else:
            B-=1
            total+=x[1]
print(total)

 

★ 두 수간의 차로 정렬한 뒤(lambda 사용), 각 상점의 품목 개수가 다다랐는지에 따라 결정 → 진행하면 끝!

---