[알고리즘] 그리디 - 백준 1789 1449 11501 15903 2112
알고리즘
2023. 3. 5. 14:18
그리디
그리디는 현재 순간에서 최고의 선택을 하는 알고리즘
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]))
문제 이해하는데 좀 걸리긴 했다.
'알고리즘' 카테고리의 다른 글
[알고리즘] 정렬 - 백준 1181 3273 2075 11497 2170 (0) | 2023.03.06 |
---|---|
[알고리즘] DFS/BFS - 백준 2644 4963 2667 7562 16234 (0) | 2023.03.06 |
[알고리즘] DP(Dynamic Programming) - 백준 17202 9655 2579 2156 2565 1967 3020 (1) | 2023.03.04 |
[알고리즘] 이진 탐색(Binary Search) - 백준 10816 2512 2805 16564 2467 1339 7576 (0) | 2023.03.01 |
[알고리즘] 정렬 - 백준 2750 1920 2108 1946 2470 1461 10026 (0) | 2023.02.28 |