๋ฌธ์
ํ์ฐธ์ ๊ณ ๋ฏผํ ๊ณผ์ ๋ฌธ์ . ๊ฒฐ๊ตญ์๋ ๋ค๋ฅธ ์ฌ๋์ ํ์ด๋ฅผ ๊ฒ์ํด์ ํํธ๋ฅผ ๋ณด๊ฒ ๋์๋ค.
- ํํธ : ๋ฐฑ์ค โํ์์ค ๋ฐฐ์ โ ๋ฌธ์
ํ์์ค ๋ฐฐ์ ์ ํ์ด์ฌ์ผ๋ก ํ์ด๋ณธ ์ ์ด ์์ด, ํ์ด์ฌ์์ ์ด๋ค ์์ผ๋ก sort๋ฅผ ์ปค์คํ ํด์ฃผ๋ ์ง ๊ถ๊ธํด์ ์ฐพ์๋ณด์๋๋ ํํ๋ก ์ฌ๋ฌ ์ธ์๋ฅผ ์ฃผ๋ฉด ํด๋น ์ธ์์ ์์๋๋ก ์ ๋ ฌ์ ํด์ค๋ค๊ณ ํ๋ค. ๊ฐ๋ น Nํ 2์ด์ ๋ฐฐ์ด arr๋ฅผ arr[1]์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๊ณ ๊ฐ์ด ๊ฐ์ผ๋ฉด arr[0]์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌ ํ๋ ๊ฒฝ์ฐ์๋ ๋ค์๊ณผ ๊ฐ๋ค.
arr.sort(key = lambda x : (x[1], x[0]))
์ค.. ๋งค์ฐ ์ ๊ธฐํ๋ค. ๊ทธ๋ผ ๋ง๊ฐ์ผ ์์ผ๋ก ๊ฑฐ๊พธ๋ก ๊ทธ๋ฆฌ๋๋ฅผ ํ๋ ํ์์ค ๋ฐฐ์ ์ ๊ธฐ๋ฐ์ผ๋ก ๋ฌธ์ ๋ฅผ ๋ค์ ๋์ ํด๋ด ๋๋ค.
๋ต
๋ถํ์ํ๊ฒ ๊ธธ๊ฒ ํผ ๊ฒ ๊ฐ์ง๋งโฆ ์ด๋ป๊ฒ ๋ ํจ์จ์ ์ผ๋ก ํ ์ ์๋์ง๋ฅผ ์ ๋ชจ๋ฅด๊ฒ ๋ค.
# ํ๋ฃจ์ ํ ๊ณผ์ ๋ฅผ ๋๋ผ ์ ์๋๋ฐ,
# ๊ณผ์ ๋ง๋ค ๋ง๊ฐ์ผ์ด ์์ผ๋ฏ๋ก ๋ชจ๋ ๊ณผ์ ๋ฅผ ๋ชป๋๋ผ ์๋ ์์.
# ๊ฐ์ฅ ์ ์๋ฅผ ๋ง์ด ๋ฐ์ ์ ์๋๋ก ๊ณผ์ ๋ฅผ ์ํํ๊ณ ์ถ๋ค.
# N : ๊ณผ์ ์ ๊ฐ์
# d : ๊ณผ์ ๋ง๊ฐ์ผ๊น์ง ๋จ์ ์ผ์
# w : ๊ณผ์ ์ ์ ์
from collections import deque
import copy
def _13904() :
ans = 0
N = int(input())
works = [[0]*2 for _ in range(N)]
for i in range(N) :
works[i][0], works[i][1] = map(int, input().split())
works.sort(key = lambda x : (-x[0], -x[1]))
works = deque(works) # popleft๋ฅผ ์ฐ๊ธฐ ์ํจ (deque์ popleft๋ O(1)์ด๋ค.)
maxDay = (works[0])[0] # ์ต๋ ๋ง๊ฐ์ผ
while works :
if maxDay <= 0 : break
todayWork = [] # maxDay์ ํ ์ ์๋ ์์
๋ฐฐ์ด
tempWorks = copy.deepcopy(works)
for work in tempWorks :
if work[0] >= maxDay :
todayWork.append(works.popleft())
else : break
if todayWork :
todayWork.sort(key = lambda x : (-x[1]))
todayWork = deque(todayWork)
ans += (todayWork.popleft())[1]
works = list(works) + list(todayWork)
works = list(works)
works.sort(key = lambda x : (-x[0], -x[1]))
works = deque(works)
maxDay -= 1
return ans
print(_13904())
์ด ๋ธ๋ก๊ทธ ์์ ํ์ด๋ฅผ ๋ณด๋ ์งง๊ณ ์์๊ฒ ํ๋ ค์์ต๋๋ค.
ํ๋ํ๋ ์ดํด๋ณด๋ฉด, ๋ฑํ deque๋ก ์ ์ธํ์ง ์๊ณ sort๋ฅผ ํด์ฃผ์๋ค์. ์ ์ด์ ํํ๋ก ๋ฃ์ด์ฃผ๊ณ deque๋ก ํ๋ ๋์ ๋ด๋ฆผ์ฐจ์ ๊ทธ๋๋ก ๋ค์์๋ถํฐ ๊บผ๋๋ค์โฆ! ๋๋ฅด๋ฅด
homeworks์ด ๋จ์์๊ณ , homeworks์ ๋งจ ๋์ด date๋ณด๋ค ํฌ๋ฉด ๊ณ์ ๊บผ๋ด์ค๋๋ค. ์๊ณ ๋ฆฌ์ฆ ์์ฒด๋ ์ ์ฌํ๋ฐ ์ ์ฒ๋ผ ๋ถํ์ํ ๊ณผ์ ์ ์๊ฑฐ์น๋ค๋ ์ ์์ ํจ์ฌ ์๋๊ฐ ์๋์ฌ ๊ฒ ๊ฐ์ต๋๋ค.