[알고리즘] 그리디 - 백준 1789 1449 11501 15903 2112

그리디

그리디는 현재 순간에서 최고의 선택을 하는 알고리즘

 

1789 수들의 합

 

s = int(input())
 
hap = 0
ans = 0
 
while s >= hap:
    ans += 1
    hap += ans
    if s < hap:
        break
print(ans - 1)

 

1449 수리공 항승

 

n, l = map(int, input().split())
leak = list(map(int, input().split()))
 
leak.sort()
 
start = leak[0]
cnt = 1
 
for x in leak[1:]:
    if x in range(start, start + l):
        continue
    else:
        start = x
        cnt += 1
        
print(cnt)

 

11501 주식

t = int(input())
 
for _ in range(t):
    n = int(input())
    stock = list(map(int, input().split()))
    pointer = 0
    
    maxi = 0
    val = 0
    for i in range(len(stock)-1, -1, -1):
        if stock[i] > maxi: # 주식 막날이 젤커
            maxi = stock[i] # 제일 큰값이 막날값
        else:   # 주식 날이 맥시멈보다 작아
            val += maxi - stock[i]  # 팔아
        
    print(val)

 

 

15903 카드 합체 놀이

n, m = map(int, input().split())
 
cards = list(map(int, input().split()))
 
cards.sort()
 
for i in range(m):
    cards[0] = cards[0] + cards[1]
    cards[1] = cards[0]
    cards.sort()
    
print(sum(cards))

 

2112 센서

n = int(input())
k = int(input())
 
sensor = list(map(int, input().split()))
 
sensor.sort()
 
# 3  6 7 8  10 12  14 15  18 20
# 1 3  6 6 7 9   
 
gap = []
 
for i in range(n-1):
    gap.append(sensor[i+1] - sensor[i])
    
gap.sort()
 
print(sum(gap[:n-k]))

문제 이해하는데 좀 걸리긴 했다.