★Greedy Intermediate II - 4 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

---