★Greedy Intermediate II - 11 Solved★

★ 2012 등수 매기기 ★

 

import sys
input=sys.stdin.readline
N=int(input())
ans,i=0,1
for x in sorted([int(input()) for _ in range(N)]):
    ans+=abs(x-i)
    i+=1
print(ans)

 

💲 greedy 알고리즘은 직관적으로 optimal solution의 모음 → 전체 최적 solution이라 생각하고 진행하는 경우가 많다.

 

💲 greedy 관점 분석

: 개별 상황) 각자 예상한 등수에 실제 등수 부여, 그리고 불만도 구하기

: 종합 상황) 불만도의 합 / 최적의 종합 상황) 불만도의 합이 최소

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 먼저 예상한 등수를 ascending order 정렬 / 실제 등수를 1부터 ascending order에 맞게 부여하면 불만도의 합이 최소

---

★ 1049 기타줄 ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
six,one=map(min, zip(*(map(int, input().split()) for _ in range(M))))
ans=0
if six > one*6: print(N*one)
else:
    ans+=(N//6)*six
    if (N%6)*one > six: ans+=six
    else: ans+=(N%6)*one
    print(ans)

 

💲 greedy 관점 분석

: 개별 상황) 패키지로 살 지, 낱개로 살 지 결정

: 종합 상황) 결정 결과의 합계 / 최적의 종합 상황) 합계 가격이 최소

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 (1) 낱개를 6개 모은 것보다 패키지가 더 비싸다면, 낱개로만 무조건 구매 / (2) 패키지가 더 싸다면 일단 패키지로 6으로 나눈 몫만큼 사고, 패키지로 살 수 없는 낱개인 경우 패키지 1개로 사는 게 이득일지, 낱개로 사는 게 이득일지 결정 (위 (1)과 (2) 구별에 greedy 원리)

---

★ 2847 게임을 만든 동준이 ★

 

import sys
input=sys.stdin.readline

N=int(input())
levels=[int(input()) for _ in range(N)]
cnt,cur=0,levels[-1]-1
for level in levels[::-1][1:]:
    if level < cur:
        cur = level-1
    else:
        cnt+=(level-cur)
        cur=cur-1
print(cnt)

 

💲 greedy 관점 분석

: 개별 상황) 각 숫자별로 얼마만큼 감소시킬지 결정

: 종합 상황) 총 감소 카운트 합계 / 최적의 종합 상황) 감소 카운트 합계 최솟값

 

★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션은 거꾸로 오른쪽부터 맨 오른쪽 숫자는 놔둔 채로 그 앞부터 1씩만 감소한 숫자로만 구성되게끔, 만약 1보다 감소한 숫자보다도 더 작다면 그 숫자를 기준으로 1씩 감소하며 왼쪽으로 계속 진행(오른쪽부터 거꾸로 진행하면서 if문으로 현재 cur과 level 비교: cur은 그 다음 대상 숫자)

---

★ 23895 Allocation ★

 

import sys
input=sys.stdin.readline

T=int(input())
for i in range(1,T+1):
    N,B=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    ans=0
    for a in A:
        if a<=B:
            B-=a
            ans+=1
            if B<=0:
                break
    print(f'Case #{i}: {ans}')

 

💲많은 개수의 집을 사려면 일단 싼 집부터 먼저 get

---

★ 1439 뒤집기 ★

import math
S,x=input(),0
for i in range(1,len(S)):
    if S[i]!=S[i-1]:x+=1
print(math.ceil(x/2))

 

💲1과 0 이렇게 다른 부분의 개수를 구하고 math.ceil(다른 부분의 개수/2)를 구하면 끝. 예를 들어 101이 있을 때 바뀐 부분은 2개 이므로 절반 횟수만큼 바꾸어 주어야 원하는 대로 바뀜. 따라서 절반으로 나누어야 한다.

---

★ 30457 단체 줄넘기 ★

import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
A.sort()
B=[]
a,b=1,0
for x in range(1,len(A)):
    if A[x]>A[x-1]: a+=1
    else:
        B.append(A[x])
if len(B)!=0:
    b=1
    for x in range(1,len(B)):
        if B[x]>B[x-1]: b+=1      
print(a+b)

 

💲양 방향을 바라볼때 키가 작은 사람 쪽만 바라볼 수 있으므로 같은 키를 가진 사람은 양 쪽 최대 2자리만 놓을 수 있다는 사실만 알면 된다! 먼저 오름차순으로 쭉 정렬. 같은 키를 가진 나머지 사람들을 오른쪽 끝부터 배치하되 여기서도 동일한 키가 있으면 제외.

---

★ 30873 Hanyang Popularity Exceeding Competition ★

import sys
input=sys.stdin.readline

N=int(input())
popularity=0
for _ in range(N):
    P,C=map(int,input().split())
    if abs(P-popularity)<=C:
        popularity+=1

print(popularity)

 

💲단순하게 직접 최대한 많이 만나는 것이 중요하므로, 만날 때마다 (순서는 차례대로 이미 정해져 있음) abs(P-popularity)<=C 식 맞는 지 점검. 만나는 사람마다의 가중치는 모두 동일하므로 단순하게 popularity += 1씩 증가하면서 최종 popularity 출력

---

★ 14655 욱제는 도박쟁이야!! ★

import sys
input=sys.stdin.readline

N=int(input())
round1=list(map(int,input().split()))
r1=[-x if x < 0 else x for x in round1]
round2=list(map(int,input().split()))
r2=[-x if x > 0 else x for x in round2]
print(sum(r1)-sum(r2))

 

💲 첫번째 라운드에서 최댓값을 가질려면 모든 값은 최대한 음수가 아닌 양수쪽 / 두번째 라운드는 그 반대

💲 제일 끝에 1개 또는 2개만 뒤집어도 되므로, 곧 모든 동전을 원하는 대로 양수쪽이나 음수쪽으로 뒤집을 수 있다는 뜻. 따라서 모두 양수 - 모두 음수일때 바로 연산해주면 된다.

---

★ 20937 떡국 ★

import sys
input=sys.stdin.readline
from collections import Counter

N=int(input())
cs=list(map(int,input().split()))
cs=sorted(cs,reverse=True)
ans=0
x=Counter(cs)
x_freq=x.values()
print(max(x_freq))

 

💲 떡국 그릇 탑은 내림차순 수열 그 자체를 뜻한다. 예를 들어 [5, 4, 3, 2, 2, 1, 1]이 있다면, 탑의 개수를 최소화할려면 [5, 4, 3, 2, 1] [2, 1] 이렇게 2개로 만들 수 있다. 즉 한 개의 탑 내에 내림차순 숫자 개수를 많이 넣으면 된다. 즉, 탑의 개수는 Counter() 활용하여 최빈값의 최댓값을 구하면 된다.

---

★ 31066 비 오는 날 ★

import sys
input=sys.stdin.readline

for _ in range(int(input())):
    N,M,K=map(int,input().split())
    if N!=1 and (M,K)==(1,1):
        print(-1)
        continue
    status=[N,M,0,0]
    ans=0

    while status[1]!=0:
        #1st go
        ans+=1
        if (status[0]-status[1]*K)<=0:
            print(ans)
            break
        else:
            status=[status[0]-status[1]*K,0,status[1]*K,status[1]]

        #2nd come back again
        ans+=1
        status[2] -= 1
        status[0] += 1
        status[1] += status[3]
        status[3] = 0

 

💲모든 학생이 건너가기 위한 시행 최소 횟수. 우산 개수 * 들고 갈 수 있는 사람의 수만큼 모두 가고, 모두 가져가지 못하면 한 명 모두 우산 들고오게끔 직접 시뮬레이션 돌리면 된다.

---

★ 30796 gahui and sousenkyo 4 ★

import sys
input=sys.stdin.readline
v,k=map(int,input().split())
cnt=0
start=v
l1,ans=[],[]
while start>0:
    if (start-k)<=0:
        ans+=[x for x in range(start,0,-1)]
    else:
        ans+=[x for x in range(start,start-k,-1)]
    start=(start-k-k)
ans.sort(reverse=True)
print(len(ans))
print(*ans,sep='\n')

 

💲그리디 관점으로 start부터 업데이트를 해나가며 선거에 출마하는 캐릭터 개수 출력

---