A | B | C | D | E1 | E2 | F | G1 | G2 |
---|---|---|---|---|---|---|---|---|
AC | AC | AC | AC | AC | AC | - | - | - |
F
, G1
์ค์ ํ๋๋ง ๋ ํ์์ผ๋ฉด, ๋ก์๊ฐ์ด์๋๋ฐ ๋๋ฌด ์์ฝ๋ค. F
, G1
๋ณต๊ธฐ ์์ .
์ ํ์ ์ธ ์ฝํฌ์คํ์ผ A๋ฒ.
Deque
๋๋์ผ๋ก, ์ ๋ค๋ก ์ซ์๋ฅผ ๋ฃ์ด ํด๊ฒฐํ๋ค.
์ ํ์ ์ธ Greedy
. prefix sum
๊ณผ prefix max
๋ฅผ ๊ตฌํด์ผ ํ๋ ๋ฌธ์ ๋ผ์ ์ฌ๋ฐ์๋ค. RPG ์ฅ๋ฅด์์ 1ํ์ฑ ํ์คํธ ์ดํ ๋ฐ๋ณตํ๋ฉด ๋ณด์์ด ์์ข์์ง๋ ๊ทธ๋ฐ ๊ฒ์ ์ฌ์ฉํด์ ๋ธ ์ฌ๋ฐ๋ ๋ฌธ์ .
ํ D๋ฒ ์ค๋ฉด ๋ณดํต ๋จธ๋ฆฌ๊ฐ ์ ์๋์๊ฐ๋ค. ๊ทธ๋์ ๊ฐ ํ๋ ์ค ์ด๋์ธ ๊ฒ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํด์ ๋งํผ ๋ฐ๋ณตํ๋๋ฐ, ์๊ณ ๋ณด๋ ๋ฒ๋ง ๋ฐ๋ณตํด๋ ๋๋ค.
์ญ์๋ Greedy
. ๊ฐ ํ๋ ์ด์ด๊ฐ ์ต์ ์ผ๋ก ๊ฒ์ํ๋ค๋ฉด, ๊ฐ ์ต๋ํ ๊ฒ์ ๊ณ ๋ฅด๋ฉด ๋๋ค. ์ด ์ฌ์ค์ ์๊ณ ๋๋ฉด, ๊ทธ๋ฅ ํ๋ฒํ pq
๋ฌธ์ ๋ก ๋ณํ๋ค.
๋ญ๊ฐ ์์ฒญ ๋ณต์กํ tree ๋๋๊ธฐ ํฉ์น๊ธฐ๋ก ๊ตฌํ์ ์๋ํ๋ค๊ฐ ๋งํ๋๋ฐ, ์ ์๋น ์์ .
๋ญ๊ฐ ํ ๋งํ ๊ฒฝ์ฐ์ ์ ๊ตฌํ๊ธฐ๋ผ๋ ๊ฒ ๊ฐ์๋ฐ ์ง๊ธ์ ์ ๋ชจ๋ฅด๊ฒ ๋ค. ์ถํ ํ์ด ์์ .
Skip.