★Greedy Advanced I - 5 Solved★

★ 1744 수 묶기 ★

 

import sys
input=sys.stdin.readline

N=int(input())
arr=[int(input()) for _ in range(N)]
ans=0
pos,neg,zero,one=[],[],[],[]
for n in arr:
    if n==0: zero.append(0)
    elif n==1: one.append(1)
    elif n>0: pos.append(n)
    else: neg.append(n)
#1. don't tie ones
ans+=len(one)

#2.tie pos(from the biggest)
pos.sort(reverse=True)
for i in range(0,len(pos),2):
    if i==len(pos)-1:ans+=pos[i]
    else:ans+=(pos[i]*pos[i+1])

#3.tie neg(from the smallest, if one left, if zero exists, don't add or add)
neg.sort()
for i in range(0,len(neg),2):
    if i==len(neg)-1:
        if len(zero)==0: ans+=neg[i]
    else:ans+=(neg[i]*neg[i+1]) 
print(ans)

 

🦛 문제 설명, 두 개로 묶어서 두 개의 수를 곱하거나, 그대로 놔두거나, 둘 중 1개를 택해서 연산 결과 최댓값

 

🦛 greedy 관점 분석

: 개별 상황) 인접한 왼쪽 또는 오른쪽 수와 묶을 지 / 안 묶을 지 결정

: 종합 상황) 각각의 항(묶은 mulsum 또는 개별) 합 구하기 / 최적의 종합 상황) 합 최댓값

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 (1) 양수일 경우(1 제외) / (2) 음수일 경우 / (3) 0일 경우 / (4) 1일 경우 : 4가지의 상황으로 나눌 수 있다.

 

★ 두 수간의 연산에서 총 아래와 같은 10가지 상황으로 나오게 되는데

① 1 제외 양수와 1 제외 양수: 곱 우선

② 1 제외 양수와 음수: 합 우선

③ 1 제외 양수와 0: 합 우선

④ 1 제외 양수와 1: 합 우선

⑤ 음수와 0: 곱 우선

⑥ 음수와 1: 합 우선

⑦ 음수와 음수: 곱 우선

⑧ 0과 1: 합 우선

⑨ 0과 0: 합 우선

⑩ 1과 1: 합 우선

 

▶ 1이 들어가는 ④⑥⑧⑩ 4개의 case는 무조건 합이 우선되므로 묶을 일이 없다. 따라서 (#1. 먼저 1만 빼놓고 1의 개수를 더한다.)

▶ 위와 같이 묶어야 하는 pair 종류는 정확히 세 쌍이다. 곱이 합보다 우선되므로 case ①의 1제외 양수는 ⑤와 ⑦에 해당되지 않으므로 (#2. 먼저 1제외 양수만 list로 빼서 pair간의 mulsum을 구한다.(이 때 sorting해서 큰 수부터 차례대로 감소 순(greedy)으로 여러 pair씩 골라 mulsum / 만약 1제외 양수가 1개 남는다면 나머지 종류와 엮지 말고 그대로 합)

▶ 중요한 건 case ⑤와 case ⑦인데, 음수가 두 case에 겹친다. 이 중에 먼저 우선되는 건(greedy) 음수와 음수의 곱인 case ⑦ 이다. 음수와 음수를 곱하면 0이 안나오고 양수가 나오므로 더 큰 결과가 나옴. 따라서 greedy하게 case ⑤를 먼저 풀기 위해 (#3. 위 1 제외 양수간의 곱 case ①처럼 먼저 음수만 list로 빼서 pair간의 mulsum을 구한다.(이 때 sorting해서 작은 수부터 차례대로 증가 순(greedy)으로 여러 pair씩 골라 mulsum)

▶ 그 다음 남은 case 중 case ⑦이 우선되므로(greedy), (#3. 위 case ⑤에서 음수가 1개 남았고 0이 있는 상태라면 곱 반영 / 만약 음수가 1개 남았는데 0이 없다면 그대로 합)

▶ 곱을 해야하는 위 세가지 case를 모두 살펴보았으므로 나머지 숫자들은 0만 남음. the end.

---

★ 12904 A와 B ★

 

S=input()
T=input()
l=len(S)

while 1:
    if len(T)==l:
        if T==S: print(1)
        else: print(0)
        break

    if T[-1] == 'A':
        T=T[:-1]
    else:
        T=T[:-1][::-1]

 

🦛 S → T를 T → S로 방향을 바꾸면

① 끝의 문자가 A인 경우: 문자열의 뒤에 A를 추가한다 → A를 그저 제외한다

② 끝의 문자가 B인 경우: 문자열을 뒤집고 뒤에 B를 추가한다 → B를 제외하고 뒤집는다

: 이미 A가 붙는 경우, B가 붙는 경우가 차례대로 문자열을 완성하면서 정해져 있음. 위의 동그라미 경로대로 T라는 문자열이 만들어지기까지의 과정 속 문자열들이 이미 정해짐 / S라는 문자열의 길이가 같을 때 T를 거꾸로 돌아 같다면 바로 1 출력, 같지 않다면 나올 수 없는 문자열이므로 0 출력

---

★ 30805 사전 순 최대 공통 부분 수열 ★

 

import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
M=int(input())
B=list(map(int,input().split()))
nums=[y for y in range(100,0,-1)]
ans=[]
while True:
    flag=False
    for num in nums:
        if num in A and num in B:
            flag=True
            x=num
            ans.append(int(num))
            break
    if not flag:
        break
    a,b=A.index(x),B.index(x)
    A,B=A[a+1:],B[b+1:]

print(len(ans))
if len(ans) > 0:
    print(*ans)

 

🦛 사전 순 나중인 기준을 보면 ① 무조건 긴 수열이 나중 / ② 길이가 같다면 가장 앞에 있는 숫자가 큰 수열이 나중

: 따라서 가장 큰 숫자인 100부터 시작해서 공통으로 갖고 있는 수라면, '왼쪽 기준 먼저 등장하는 숫자'를 고르는 greedy한 관점으로 사전 순 공통 부분 수열을 구할 수 있다. 예를 들어 100 100 100 50이 있고 100 100 50이 있다면, 길이가 긴 수열이 무조건 나중이므로 왼쪽 기준 먼저 등장하는 공통 최댓값 숫자를 골라야 한다. 고르면 그 앞의 숫자들은 greedy 원리에 의해 정답 x. 오른쪽 이후 남은 숫자들만 골라서 다시 slicing 하고 반복적으로 진행

---

★ 7983 내일 할거야 ★

 

import sys
input=sys.stdin.readline

dts=[]
for _ in range(int(input())):
    d,t=map(int,input().split())
    dts.append((d,t))

dts=sorted(dts,key=lambda x: x[1], reverse=True)
ans=dts[0][1]

for pair in dts:
    if ans > pair[1]:
        ans = pair[1] - pair[0]
    else: #ans <= pair[1]
        ans = ans - pair[0]
print(ans)

 

🦛 greedy 2번 적용

① 과제 가능 시간 t에서 과제를 하는 시간은 greedy에 의해 최대한 끝 부분에서 연속으로 앞으로 과제 시행이 최적 (최대한 노는 걸 원하므로 끝에서부터 과제를 시행하게 해야 함)

② 여러 과제가 있다면 greedy에 의해 과제 가능 시간 t가 제일 긴 것부터 먼저 t 끝에서 과제를 시행하는 게 최적 (과제 가능 시간이 긴 과제를 먼저 끝에서 해주어야 최대한 앞에서 많이 놀 수 있음)

→ 따라서 각 과제를 t 감소순으로 나열하고, 해당 과제 t에서 d를 빼는 걸 최선으로 선택. 만약 현재 끝 지점이 해당 과제 t보다 작거나 같다면 현재 끝 지점에서 d를 빼는 걸 최선으로 선택

: 각 과제의 오른쪽 끝부터 시작하는 게 최적이나, 위 10 과제에서 3을 먼저 해결하고 나면 7이 되어 8 과제와 겹침. 따라서 8이 아닌 7에서 시작해 2를 빼야 함.

---

★ 23559 밥 ★

import sys
input=sys.stdin.readline

N,X=map(int,input().split())
choice_A_num = int((X-1000*N)/4000)
menus=[]
for _ in range(N):
    menus.append(tuple(map(int,input().split())))
menus.sort(key=lambda x:-(abs(x[0]-x[1])))
ans=0
choice_A_cnt=0
for i in range(N):
    if menus[i][0] <= menus[i][1]:
        ans+=menus[i][1]
    else:
        if choice_A_cnt<choice_A_num:
            ans+=menus[i][0]
            choice_A_cnt+=1
        else:
            ans+=menus[i][1]
print(ans)

 

🦛 5000원 메뉴와 1000원 메뉴 중 1개는 반드시 선택. 이 때 써야 하는 금액 X는 정해져 있음. 따라서 그리디 관점에서 5000원 메뉴 맛을 A, 1000원 메뉴 맛을 B라 한다면 A<=B일 경우 당장 1000원 메뉴 선택이 전체 구매 금액을 최소화함. 하지만 A>B일 경우 5000원 메뉴를 당장 선택하는 경우가, 다른 경우를 고려해서 금액이 최소가 아닐 수가 있다. 예를 들어 맛이 3과 1 / 300과 299 이렇게 두 옵션이 있다고 할 때 300 > 299라고 해서 당장 큰 300을 고른다고 하면, 금액 상 3이 아닌 1을 선택하는데 그렇다면 301, 하지만 반대로 3을 선택하고 299를 선택하면 302가 되므로 오히려 5000원 메뉴를 300보다 3이 선택한 경우가 더 최적이다. 따라서 그리디 관점으로 해결하는 방법은, 어차피 A와 B중 하나를 선택해야 하므로 |A-B|를 내림차순으로 정렬해서 |A-B|가 가장 큰 경우부터 A를 정해준다. 절댓값이 큰 경우가 최대의 맛을 볼 수 있기 때문. 이미 적어도 B는 다 먹으므로 맛을 최대로 내려면 B로부터 차이가 많이 나는 케이스부터 고려하는 게 최적.

 

🦛

(1) |A-B| 내림차순 정렬, 전체 사용 금액이 정해져 있으므로 B보다 A를 먼저 선택할 수 있는 횟수(위 choice_A_num) 구하기

(2) A<=B인 경우는 무조건 B 선택

(3) A>B인 경우는 |A-B| 큰 순으로 choice_A_num이 0보다 큰 동안 A 선택 → choice_A_num을 다 쓰면  B 선택

---