★Greedy Upper-Beginner I - 9 Solved★

★ 10162 전자레인지 ★

 

T=int(input())
a=T//300
flag=0
for i in range(a,-1,-1):
    after_A=T-i*300
    b=after_A//60
    for j in range(b,-1,-1):
        after_B=after_A-j*60
        if after_B%10==0:
            flag+=1
            k=after_B//10
            print(i,j,k)
            break
    if flag==1:
        break
if flag==0:print(-1)

 

🍇 greedy 관점 분석

: 개별 상황) A / B / C 버튼을 누르는 상황

: 종합 상황) A / B / C 버튼을 여러 번 눌러 T time에 딱 맞게 요리하기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 A버튼을 우선적으로 → B버튼 → C버튼을 누른다. (시간 효율을 위해 구하면 바로 break문)

 

🍇 먼저 300초로 나눠진다면, 그다음 100초로 나눠지는 지 확인하고, 마지막으로 10으로 나눠지는 지 차례대로 확인. 

→ greedy한 문제이므로, 300초로 나눈 몫이 큰 것부터 0까지 거꾸로 차례대로 확인하다가 답이 나오면 print()하고 바로 break!

---

★ 3578 Holes ★

 

h=int(input())
if h==0:print(1)
elif h==1:print(0)
else:
    if h%2==0:print('8'*(h//2))
    else:print('4'+'8'*(h//2))

 

🍇 greedy 관점 분석 (개별 상황이 분기문으로 나누어짐)

: 개별 상황) hole을 만들기 위해 0/4/6/9/8중 한 개 숫자를 누르는 상황

: 종합 상황) 숫자를 여러 번 눌러 만든 숫자가 최솟값으로 나오고 / 누르는 개수 h가 최솟값이 되게끔 만들기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고

→ 개별 상황의 최적 greedy 솔루션: 누를 때 8을 우선적으로 누르되, h가 홀수일 경우 4를 먼저 누르고 이후 8 누르기 (h가 0과 1만 예외)

 

🍇 구멍이 생기는 숫자 0,4,6,9,8의 조합으로만 만들어야 하고, 맨 앞에 0이 두 번 연속 올 수 없다.

 

🍇 최솟값으로 만들어야 하므로 자릿수가 최소여야 한다. 따라서 8로 최대한 구성이 되어야 함 (greedy)

① 홀수개수의 hole을 만들어야 한다면 8을 최대한 채우고, 마지막 개수 1개는 가장 최솟값인 4 - 즉 48888~ 형태여야 한다.

② 짝수개수의 hole을 만들어야 한다면 8로만 구성되어야 한다.

③④ hole이 없다면 1, hole이 1개 있다면 1

---

★ 2720 세탁소 사장 동혁 ★

 

for _ in range(int(input())):
    C=int(input())
    print(C//25,(C%25)//10,((C%25)%10)//5,C%5)

 

🍇 greedy 관점 분석

: 개별 상황) 쿼터 / 다임 / 니켈 / 페니 중 한 화폐의 종류를 선택해 돈을 거슬러 주는 상황

: 종합 상황) 주어진 돈을 여러 화폐로 거슬러 주는 상황 / 누르는 개수 h가 최솟값이 되게끔 만들기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고

→ 개별 상황의 최적 greedy 솔루션: 쿼터 - 다임 - 니켈 - 페니 순으로 먼저 종류를 선택

 

🍇 동전의 개수를 최소화 해야하므로 쿼터 - 다임 - 니켈 - 페니 순으로 greedy하게 제일 큰 금액부터 개수를 count한다

---

★ 14720 우유 축제 ★

 

import sys
input=sys.stdin.readline

N=int(input())
l=list(map(int,input().split()))
t=0
direction=0
for i in l:
    if direction==0 and i==0:
        t+=1
        direction+=1
    elif direction==1 and i==1:
        t+=1
        direction+=1
    elif direction==2 and i==2:
        t+=1
        direction-=2
    
print(t)

 

🍇 greedy 관점 분석

: 개별 상황) 각 우유가게에서 딸기 / 초코 / 바나나 / x(안 마심) 중 한 개를 선택해 마시는 상황

: 종합 상황) 모든 우유가게에서 각각의 우유를 다양하게 선택해 마시는 상황 / 마시는 우유 개수가 최댓값이 되게끔 만들기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고

→ 개별 상황의 최적 greedy 솔루션: 각 가게에서는 우유를 1번만 마실 수 있으므로 마시는 규칙이 성립한다면 '바로' 그 가게에서 마심. (X를 선택하지 않고 마시는 솔루션)

 

🍇 마실 수 있다면 바로 마시는, greedy 유형! direction 방향 변수를 사용해, direction 변수에 맞는 값이라면 바로 마시게끔 코드 짬

 

🍇 방향변수를 사용한 코드 기억하자!

---

★ 17931 Greedily Increasing Subsequence ★

 

import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
ans=[A[0]]
l=1
cur=A[0]
for ai in A[1:]:
    if ai>cur:
        ans.append(ai)
        l+=1
        cur = ai
print(l)
print(*ans)

 

🍇 greedy 관점 분석

: 개별 상황) Subsequence를 만들기 위해 현재의 숫자를 subsequence에 넣을 지 안 넣을 지 결정하는 상황

: 종합 상황) Greedily Increasing Subsequence를 만드는 상황

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고

→ 개별 상황의 최적 greedy 솔루션: 현재 Cur 값보다 큰 값이면 subsequence에 넣기를 선택

---

★ 5585 거스름돈 ★

 

n=0
money=1000-int(input())
for x in [500,100,50,10,5,1]:
    n+=(money//x)
    money%=x
print(n)

 

🍇 greedy하게 큰 화폐 단위부터 먼저 카운트. 그래야 최종 화폐 지폐 개수 최소화 가능

---

★ 4796 캠핑 ★

 

import sys
input=sys.stdin.readline
i=0
while 1:
    i+=1
    L,P,V=map(int,input().split())
    if (L,P,V)==(0,0,0):break
    print(f'Case {i}: {(V//P)*L+min(L,V%P)}')

 

🍇 greedy 관점 분석

: 개별 상황) 각 일수 별로 캠핑을 갈 지, 말 지 결정

: 종합 상황) 캠핑장을 가는 날 수 총 더하기

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고

→ 개별 상황의 최적 greedy 솔루션: 캠핑장 가는 최대 일수(최대한 각 P일 중 1일부터 L일까지 쭉 간 다음, 그 다음 P일에서도 1일에서 L일까지 갈 수 있게 한다. 주어진 P일에서 최대 L일을 꽉꽉 채우는 게 각 P일에서의 greedy한 결정. 후반에 간다면 다음 P일에서의 L일과 겹쳐 캠핑을 못 갈 수 있으므로 1일부터 몰아 가게 해야 최대 L일을 꽉꽉 채움 + 나머지는 L일과 비교해서 min값 추가)

---

★ 2864 5와 6의 차이 ★

 

A,B=input().split()

a1,b1=A.replace('6','5'),B.replace('6','5')
a2,b2=A.replace('5','6'),B.replace('5','6')

print(int(a1)+int(b1),int(a2)+int(b2))

 

🍇 greedy 관점 분석

: 개별 상황) 5와 6을 만나면 각각 5로 바꿀 지, 6으로 바꿀 지 결정

: 종합 상황) 두 수의 합

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고

→ 개별 상황의 최적 greedy 솔루션: 최솟값은 모든 6을 5로, 최댓값은 모든 5를 6으로 (replace()로 한번에)

---

★ 30019 강의실 예약 시스템 ★

 

🍇 현재 시점에서 당장 강의가 먼저 열리는 강의를 선택하므로 greedy적 접근. cur list에 각 강의실의 끝 시간을 update. s가 임박한 순으로 주어지므로 각 line 진행하면서 현재의 e와 비교해 YES / NO 출력

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
cur = [0 for _ in range(N)]

for _ in range(M):
    k,s,e=map(int,input().split())
    if s >= cur[k-1]:
       print('YES')
       cur[k-1]= e
    else:
        print('NO')

---