๐
TIL์ ์์ฆ ๋๋ฌด ์ ์ผ์๋ค! ํ๋ฃจ๋ฅผ ๊ธฐ๋กํ๋ ๊ฑฐ์ ์์๊ฐ ์๋ ๊ฑด๋ฐ, ๋ฐ์๋ค๋ณด๋ ๋ง์์ด ํ์ํด์ ธ์ ์๊พธ ํ๊ณ ์ ๊ธฐ๋ก์ ์๋๋ค.
ํ๋ก๊ทธ๋๋ฐ ๋ฌธ์ ํ์ด ๐ซ
-
์คํ๋ฐฐ๋ฌ : https://www.acmicpc.net/problem/2839
-
1๋ก ๋ง๋ค๊ธฐ : https://www.acmicpc.net/problem/1463
-
1,2,3 ๋ํ๊ธฐ https://www.acmicpc.net/problem/9095
-
ํผ๋ณด๋์น ํจ์ https://www.acmicpc.net/problem/1003
-
2xn ํ์ผ๋ง https://www.acmicpc.net/problem/11726
-
RGB๊ฑฐ๋ฆฌ https://www.acmicpc.net/problem/1149
์์ฒญ ์ค๋ซ๋์ ์ ํ์๋ DP๋ฌธ์ ๋ค์ ๋ค์ ํ์๋ค. ๊ธฐ๋ก์ ๋ณด๋ ๋ฌด๋ ค 1๋ ์ ์ ๋ง์ง๋ง์ผ๋ก ํ์๋ ๋ฌธ์ ๋ค์ด์๋ค. 1๋ ์ ์๋ ๊ฐ์ฅ ์์ ์์ดํ๋ ๋ถ์ผ์๊ณ , ํ๋ก๊ทธ๋๋ฐ ์ผ์ค๊ฐ ๋ถ์กฑํด์ ๊ทธ๋ ๋ค๊ณ ๋ ์์ฑ ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด์๋ค. โ์ ํ์ด๋ ํ์ด๋ ์ด๋ ค์ธ๊น?โ ํ๋ ๋ง์์ด ์ฃ์ฑ ๊ฐ์ฒ๋ผ ๋ ๋จ์์์๋๋ฐ, 1๋ ๋ง์ ๋ค์ ๋ง๋ DP ๋ฌธ์ ๋ค์ ๊ทธ๋๋ณด๋ค๋ ์์ํ๊ฒ ํ ์ ์์๋ค.
๋ ๋๋ ๊ฒ ๊ฐ์๋๋ฐ ๋์๋ณด๋ฉด ์ฑ์ฅ์ ํ๊ธด ํ๋ ๊ฒ ๊ฐ๋ค.
DP๊ฐ ๋์ ํ ์ดํด๊ฐ ์๋์ด์ ํ๋์ ๋น ๊ณต์ฑ ์ DP ๊ฐ๋ ๊ณผ ์์ ๋ฅผ ํผ์์ ๊ณต์ฑ ์ ์ ์ด๋ด๋ ค๊ฐ๋ฉฐ ๊ณ ๋ ํ ๊ฐ์๋ฅผ ํ๊ณค ํ์๋๋ฐ, ๋๋ถ์ ๊ฐ๋ ์ด๋ ํ์ด๊ฐ ๋จธ๋ฆฟ์์ ์ด๋ ์ ๋ ๋ค์ด์๋์ง ๋ด ์ฝ๋๋ฅผ ๋ฆฌ๋ทฐํ๋ฉด์๋ ํ์๋ณด๋ค๋ ์์ํ๊ฒ ๋ง์ ํ๋ค. (ํ์์ ๋ด๊ฐ ๋ฌด์จ ๋ง์ ํ๊ณ ์๋์ง๋ ์ธ์งํ ์ ์์๋ค..ใ ใ ๋งํ๋ ๊ฒ ๊ฐ์ฅ ์ด๋ ต๋ค)
๋ ธ์ ๋ง์ง์
ํ ์ผ์ด ์กฐ๊ธ ์์ด์ ๋์ด ์๊ฐ ์ ๋ ๋ ธ์ ์ ๋ง์ก๋๋ฐ, ํ ๋ฒ ๋ฃ๊ณ ๊น๋จน์๋ ์ฌ์ฉ๋ฒ๋ค์ ๋๋์ด..! ๋๋์ด ๊ธฐ์ตํ๊ธฐ ์์ํ๋ค. ์ด์ ๋ง์ผ์คํค ๋ง๋ค ์ค ์๋ค.
J2KB ํฌ๋ฃจ ํ๋์ ํ๋ฉด์ ํ์ ํ๋ก์ธ์ค๋ ๋ ธ์ ์ฌ์ฉ๋ฒ ๋ฑ์ ์ตํ๋๊ฐ๋ ๊ฒ ๊ฐ์ฅ ๋์์ด ๋๋ค. ์ข์ ๋ถ๋ค์ ์ ํ๋ค ๋ณด๋ ๋๊น์ง ๋๊ธฐ๋ถ์ฌ๋ฅผ ๋ง์ด ๋ฐ์ ๊ฐ๋ค ๐ช๐ช
ํด์ฌ
1๋ 4๊ฐ์์ ํํธํ์ด๋จธ๋ก์ ์ผํด์๋ ์ ๋ ๋ณ์์ ๋ ๋๋ฉฐ.. ๋๊ฐ๋ ๋ ์๋ ๋์์ด ๊ฐ์ดํ ๊ฒ ๊ฐ์๋๋ฐ ๊ธฐ๋ถ์ด ์ด์ํ๊ณ ์ฌ๋๋ค์ด๋ ์ธ์ฌํ๋ค๋ณด๋ ์ฌ์ ์ฌ๊ฐ ํ๊ณ ์ถ์ด์ง ์ง๊ฒฝ์ด์๋ค. ๋ฌผ๋ก ์ฌ์ ์ฌํ๋ผ๊ณ ํ๋ฉด ์ ํ๊ฒ ์ง๋งโฆ ๊ทธ๋๋ ๋ํ๊ทผ๋ฌด ์ ๋๋ ํด์ค ์ ์์ง ์์๊น ์ถ๋ค.
๋ด ์ธ์์์ ์ด๋ ๊ฒ ๋ง์ ๊ฐ์์ง์ ๊ณ ์์ด๋ค์ ๋ง๋ ์ผ์ด ์์๊น ์ถ๋ค. ์ ๋ค์๋ ๊ฐ์์ง, ๊ณ ์์ด๋ค๋ ๋๋ฌด ๋ง๋ค. ํญ์ ๊ธฐ์ตํ๋ ์ข ์ด๋ถํฐ, ํฌ๋(์ผ๋ง์ ์ ์๋ ๊ฐ์์ง์ธ๋ฐ ๋๋ฌด ์ฌ๋์ค๋ฝ๊ณ ์นํ๋ ฅ์ด ์ข์์ ๋ ๋ณด๊ณ ์ถ๋ค), ์ฝ์ฝ์ด(์ค๋ฉด ํ๋ฃจ์ข ์ผ ์ฐ๋๋ฐ ๋ฌผ๊ฑฐ๋ ํ ํด๊ฑฐ๋ ํ ์ ์ ํ๋ฒ๋ ์๊ณ ์คํ๋ ค ์ธ๋ฉด์๋ ์์ฒญ ๊ฐ๋งํ ์์ด์ ์ฐก์ฐก์ด๋ผ๊ณ ๋ถ๋ ๋ค), ํคํค, ๋ฉ์ด, ์์(๋์์ ๊ณ์ ํ๋ค์ดํ๋ฉด์๋ ๋ง์ ธ์ฃผ๋ฉด ๊ธ๋ฐฉ ์ ์ด ๋๋๋ฐ, ๊ทธ๊ฒ ์ง์ง ์ฌ๋์ค๋ฝ๋ค), ์ฅ๊ตฐ์ด, ํ์ฐ์ด, ๊ฐ๋ฃจ(๊ฐ๋ฃจ!! ์ ๋ง ์ค๋ซ๋์ ์์ฃผ ๋ณธ ๊ณ ์์ด์๋๋ฐ ์์ผ๋ก ๋ชป ๋ณผ ๊ฑฐ ์๊ฐํ๋ฉด ์ฑ์ญ์์ญํ๋ค), ์ฐ๋ฆฌ ์์ฝ์ฝ, ์ฃผ๋์ด(๋์ด ์๋ฒฝํ๊ฒ ๋๊ทธ๋๊ณ ๋ค๋ฆฌ๊ฐ ๊ธธ๋ค. ์ด์ํ๋ณผ๋๋ฉด ๊ฐ๋งํ ๋์์ ๋๋ ์์์์์ฌ์ค๋ค์ ์ณ๋ค๋ณธ๋ค) ๋ค๋ค ํ๋ณตํ๊ฒ ์ ์ง๋์ผ๋ฉด ์ข๊ฒ ๋ค.
์ ๋ํผ ์ ์ ๋ฆฌํด์ ์ด๋ฆํ๊น์ง ์น ๋ฐ๋ฉํ๋๋ฐ ๊ธฐ๋ถ์ด ๋๋ฌด ์ด์ํด์ ๋ณ์ ์ฌ๊ธฐ์ ๊ธฐ๋ฅผ ์ด์ง ๋์๋ค๋ ๋ค. ๋ฐฉ์ญ๋๋ฌธ์ ๋ ๋ฏธ๋ฌํ๊ฒ ํ๊ธฐ๋ ์๋ ์ฝ ๋์๋ ์ด๋์ปด์ปดํ ์์์ค ๋ด๋ถ๋ ์ ๋ง ์ค๋ซ๋์ ๊ธฐ์ต์ ๋จ์์์ ๊ฒ ๊ฐ๋ค. ๊นํ๋ธ๊ฐ ์์ด์ง์ง ์๋ ํ ๋ด ๋ธ๋ก๊ทธ๋ ์ ๋จ์์๊ฒ ์ง..?
์๋ฌดํผ ์ผ์์ผ์ ์ฌ์ ํ ์ถ๊ทผํ ๊ฒ ๊ฐ์๋ฐ, ์ํ๋ค๋ ์ง์ง ์ด์ํ๋ค. ์ ๋ง ์ค๋๋ง์ ๋๋ต 3์ฃผ ์ ๋๋ฅผ ์๋ฌด ์๋ฐ๋ ์ํ ์์ ์ธ๋ฐ, ์ด๋๋ ๋๋๊ฑด๊ฐ ์ถ๊ธฐ๋ ํ ์ ๋๋ก ๋ฌํ๋ค. ๊ธฐ์ต์ผ๋ก๋ ํ 6๋ ๋ง์ธ ๊ฒ ๊ฐ์๋ฐ, ์ฌ๋ ๋ ์ ์๋์ ์ ๊น๋จน๋ค๋ณด๋ ์๊ณ ๋ณด๋ฉด ๋ ์ต๊ทผ์ผ ์๋ ์๋ค
์ธํด
์ธํด๋ ๋ค๋ ๋ณผ ์ ์๊ฒ ๋๊ณ , ๊ผญ ์ฐธ์ฌํด๋ณด๊ณ ์ถ๋ ๋ฉด์ ๋ ์กํ๊ณ (๋ฉด์ ๊ด๋คํํ ์คํฐ์ง๊ณ ๋์ฌ๊ฑฐ ์๊ฐํ๋ฉด ๋ฒ์จ๋ถํฐ ์์ด์ด๋ค.. ๋ด ๋ชฉํ๋ ๋ฉด์ ์์ ๋น์ฐธํจ๊ณผ ํจ๋ฐฐ๊ฐ์ ์๊ณ ํธ๋ ํธ๋ ๋์์ ์์ผ๋ก์ ์ฑ์ฅ์ด์๋ฅผ ํ์ฐ๋ ๊ฒ์ด๋ค), ์ด์ฌ๋ ํ์ ๋๊ณ , ๋ญ๊ฐ ์ฌ๋ฌ ์ผ๋ค์ด ํ๊บผ๋ฒ์ ๋ชฐ๋ ค์ค๋ ๊ฒ ๊ฐ์์ ํ์คํฌ ๊ด๋ฆฌ๊ฐ ์ ์๋๋ค. ํ ์ผ์ด ๋ง๊ธด ํ๋ฐ ์๋ฌด๋๋ ํ ์ผ์ ์ํ๊ณ ๋๊ณ ์์ผ๋๊น.. ํ ์ผ์ด ๋ง์ ์๋ฐ์โฆ
๊ฑฐ์ ์ผ๊ธฐ์ ๋ค๋ฆ์๋ ๊ธฐ๋ก์ฅ์ด ๋์์ง๋ง, ์ด ์ญ์ ์ถํ์ ํ๊ณ ๋ฅผ ํ ๋์ ํฐ ๋์์ด ๋๋ฆฌ๋ผ ์๊ฐํ๊ณ ์ฌ๋ ค๋๋ค. ์ ๋์ ์ฑ ์ ๋ฃ๊ฑฐ๋ ํด์ผ ์ ์ด ์ค๋ ํ์ ์ด์ด์, ๋ด ์๊ฐ์ ํ ์ผ์ด ์๋ค๋ณด๋ ์ด๋ ๊ฒ๋ผ๋ ์์ฃผ ์๊ฐ์ ์ ๋ฆฌํด๋ฌ์ผ๊ฒ ๋ค!
+) ์ค๋ ๊ฐ๋ฃฝ์ด ์ง๋ ์๋ฆฌ๋ฅผ ๋ค์๋๋ฐ ๋๋ฌด ๊ท์ฌ์ ๋ค. ์ ต์ผ(๊ทธ๋ฅ J2KB ์ค์๋ง๋ก ๋ฐฉ๊ธ ๋ง๋ฆ) ๋ฉ๋ฅ์ด๋ค ํฌ์ธ์ธํ ํด๋ฌ๋ผ๊ณ ์