A | B | C | D | E | F | G |
---|---|---|---|---|---|---|
AC | AC | WA | AC | AC | - | - |
B
, C
์์
C
๋ F
, G
๋ ์
์๋น ํ์ํด๋ณด์ธ๋ค. ๊ทธ๋๋ ๋งํ๊ฑฐ ์น๊ณ ๋ D
, E
๋ฅผ ํ๋ค๋ฆฌ์ง ์๊ณ ํ ์ ์์์ด์ ๋คํ.
Do you know ๋น๊ต๋ฌธ? ์ฌ๊ธฐ๊น์ง ์ข์๋ค..
์ฌ๊ธฐ๋ถํฐ ๋ง๋ ธ๋ค. ์ฌ์ค ์ง๊ธ ์๊ฐํด๋ณด๋ฉด ๋ฒ์๊ฐ ๋ผ์ ์ ๋ 1์ฉ ์ฆ๊ฐ์์ผ์๋ ์๊ฐ๋ด์ ์๋ค์ด์ค๋๊ฑด๋ฐ.. ์ ์๋ชป๋ ์๊ฐ์ ํ๋์ง ๋ชจ๋ฅด๊ฒ ๋ค. ์์์ ์ฐจ๋ถํ ์ ๊ฐํ๋ ๋ฌธ์ .
์ด๋ผ๋ ๊ฒ์ ์ฃผ๋ชฉํด์ ํ๋ฉด ๋๊ฒ ๋ค. C++
์์๋ MOD
์ฐ์ฐ์ด ์์์ ์ ์ฉ๋๋ฉด ์์๊ฐ ๋์ค๋ฏ๋ก, MOD
๋งํผ ๋ํด์ฃผ์ด์ผ ํ๋ค.
๋ง๋ฆฐ ๋ฌธ์ 2. ์
์๋น ํด์ผํ๋ค. ์ต์์น ์์ ์๋ฐฉํฅ Greedy
.
๋๋ฌด ์ ํ์ ์ด๋ผ ์คํ๋ ค C
๋ณด๋ค ์ฌ์ ๋ค. ๋์ ํฉ์ ๊ตฌํด์ค ๋ค ์ด๋ถํ์์ ๋๋ฆฌ๋ฉด ๋๋ค.
์์ฒญ ์ ํ์ ์ด์ง ์์์ง๋ง, ๊ทธ๋๋ ํ์ด๋ฅผ ๋ ์ฌ๋ฆฌ๊ธฐ๋ ์ด๋ ต์ง ์์๋ค. BFS
๋ก ๊ฐ ์ปดํฌ๋ํธ๋ค์ id
๋ฅผ ๋ถ์ฌํด์ค ๋ค, ๋น์นธ์์ ์ธ์ ํ ๊ณณ์ ์ปดํฌ๋ํธ๊ฐ ๋ช๊ฐ ์๋์ง ๋ณด๋ฉด ๋๋ค.
๊ทธ๋ฆฌ๊ณ ์ญ์๋ ์๋ ๊ธ์ ์ณ์ฝ๋ ํ ๊ฑฐ๋ฉด ๋ค์ ๋ด์ผ..
Deque DP
๋ผ๊ณ ํ๋ค. ๋ฐฑ์ค 5977๋ ๋น์ทํ๋ค๊ณ ํ๋ DP
์ฐ์ต๊ฒธ ์ฌ์ ๋๋ฉด ์ดํด๋ณผ ์์
E
์ ์ ๋ฐ๋ ๋ฒ์ . ์ปดํฌ๋ํธ๋ฅผ ์ค๊ฐ์ ๋๋๋ค. ๋ญ๊ฐ ์ ํ์ ์ธ ๋ฌธ์ ๊ฐ์๋ฐ ์์ง์ ์ ๋ชจ๋ฅด๊ฒ ๋ค.