그리디 알고리즘 예제

https://www.acmicpc.net/problem/11399

 

두 가지 주요사항:

1. 무엇을 선택할지 : 각 순서에 누구를 배치할지

2. 어떤 순서로 선택할지 : 앞 또는 뒤에서부터 누구를 배치할지 -> 뒤에서부터 배치

N = int(input())
P = list(map(int, input().split()))

P = sorted(P)
total = 0

for i in range(N):
    total += sum(P[:i+1])
    
print(total)

 

https://www.acmicpc.net/problem/2847

 

 

두 가지 주요사항:

1. 무엇을 선택할지 : 각 레벨의 보상을 몇으로 할지

2. 어떤 순서로 선택할지 : 높은 레벨부터 보상 값을 결정하는 방향

 

N = int(input())
L = [0]*N

for i in range(N):
    L[i] = int(input())
    
count = 0
for i in range(N-2,-1,-1): # 역순으로 탐색
    if L[i]>=L[i+1]:
        count += L[i]-(L[i+1]-1)
        L[i]=L[i+1]-1

print(count)