๋ชฉ๋ก์ ์ฒด ๊ธ (1005)
๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
์ด 8๊ฐ์ ํฑ๋๋ฅผ ๊ฐ์ง๊ณ ์๋ ํฑ๋๋ฐํด 4๊ฐ ํฑ๋๋ N๊ทน ๋๋ S๊ทน ์ค ํ๋๋ฅผ ๋ํ๋ด๊ณ ์๋ค. ๊ฐ์ฅ ์ผ์ชฝ ํฑ๋๋ฐํด๊ฐ 1๋ฒ, ๊ทธ ์ค๋ฅธ์ชฝ์ 2๋ฒ, ๊ทธ ์ค๋ฅธ์ชฝ์ 3๋ฒ, ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ํฑ๋๋ฐํด๋ 4๋ฒ ํฑ๋๋ฐํด๋ฅผ ์ด K๋ฒ ํ์ ์ํค๋ ค๊ณ ํ๋ค. ํฑ๋๋ฐํด์ ํ์ ์ ํ ์นธ์ ๊ธฐ์ค์ผ๋ก ํ๋ค. ํ์ ์ ์๊ณ ๋ฐฉํฅ๊ณผ ๋ฐ์๊ณ ๋ฐฉํฅ ํฑ๋๋ฐํด๋ฅผ ํ์ ์ํค๋ ค๋ฉด, ํ์ ์ํฌ ํฑ๋๋ฐํด์ ํ์ ์ํฌ ๋ฐฉํฅ์ ๊ฒฐ์ ํ์ ํ ๋, ์๋ก ๋ง๋ฟ์ ๊ทน์ ๋ฐ๋ผ์ ์์ ์๋ ํฑ๋๋ฐํด๋ฅผ ํ์ ์ํฌ ์๋ ์๊ณ , ํ์ ์ํค์ง ์์ ์๋ ์์ ํฑ๋๋ฐํด A๋ฅผ ํ์ ํ ๋, ๊ทธ ์์ ์๋ ํฑ๋๋ฐํด B์ ์๋ก ๋ง๋ฟ์ ํฑ๋์ ๊ทน์ด ๋ค๋ฅด๋ค๋ฉด, B๋ A๊ฐ ํ์ ํ ๋ฐฉํฅ๊ณผ ๋ฐ๋๋ฐฉํฅ์ผ๋ก ํ์ ํ๊ฒ ๋๋ค. ํฑ๋๋ฐํด์ ์ด๊ธฐ ์ํ์ ํฑ๋๋ฐํด๋ฅผ ํ์ ์ํจ ๋ฐฉ๋ฒ์ด ์ฃผ์ด์ก์ ๋, ์ต์ข ํฑ๋๋ฐํด์ ์ํ๋ฅผ ..
ํฌ๊ธฐ๊ฐ N×N์ธ ์ง๋๊ฐ ์๋ค. ์ง๋์ ๊ฐ ์นธ์๋ ๊ทธ ๊ณณ์ ๋์ด๊ฐ ์ ํ์ ธ ์๋ค. ์ค๋์ ์ด ์ง๋์์ ์ง๋๊ฐ ์ ์๋ ๊ธธ์ด ๋ช ๊ฐ ์๋์ง ์์๋ณด๋ ค๊ณ ํ๋ค. ๊ธธ์ด๋ ํ ํ ๋๋ ํ ์ด ์ ๋ถ๋ฅผ ๋ํ๋ด๋ฉฐ, ํ์ชฝ ๋์์ ๋ค๋ฅธ์ชฝ ๋๊น์ง ์ง๋๊ฐ๋ ๊ฒ ๊ธธ์ ์ง๋๊ฐ ์ ์์ผ๋ ค๋ฉด ๊ธธ์ ์ํ ๋ชจ๋ ์นธ์ ๋์ด๊ฐ ๋ชจ๋ ๊ฐ์์ผ ํ๋ค. ๊ฒฝ์ฌ๋ก๋ฅผ ๋์์ ์ง๋๊ฐ ์ ์๋ ๊ธธ์ ๋ง๋ค ์ ์๋ค. ๊ฒฝ์ฌ๋ก๋ ๋์ด๊ฐ ํญ์ 1์ด๋ฉฐ, ๊ธธ์ด๋ L์ด๋ค. ๊ฐ์๋ ๋งค์ฐ ๋ง์ ๋ถ์กฑํ ์ผ์ด ์๋ค. ๊ฒฝ์ฌ๋ก๋ ๋ฎ์ ์นธ๊ณผ ๋์ ์นธ์ ์ฐ๊ฒฐํ๋ฉฐ, ์๋์ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑ ๊ฒฝ์ฌ๋ก๋ ๋ฎ์ ์นธ์ ๋์ผ๋ฉฐ, L๊ฐ์ ์ฐ์๋ ์นธ์ ๊ฒฝ์ฌ๋ก์ ๋ฐ๋ฅ์ด ๋ชจ๋ ์ ํด์ผ ํ๋ค. ๋ฎ์ ์นธ๊ณผ ๋์ ์นธ์ ๋์ด ์ฐจ์ด๋ 1์ด์ด์ผ ํ๋ค. ๊ฒฝ์ฌ๋ก๋ฅผ ๋์ ๋ฎ์ ์นธ์ ๋์ด๋ ๋ชจ๋ ๊ฐ์์ผ ํ๊ณ , L๊ฐ์ ์นธ์ด ..
๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์ฃผ์ด์ก์ ๋, ์ฒญ์ํ๋ ์์ญ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์ฅ์๋ N×M ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, 1×1ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ฐ๊ฐ์ ์นธ์ ๋ฒฝ ๋๋ ๋น ์นธ์ด๋ค. ์ฒญ์๊ธฐ๋ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ด ์์ผ๋ฉฐ, ์ด ๋ฐฉํฅ์ ๋, ์, ๋จ, ๋ถ์ค ํ๋ ์ง๋์ ๊ฐ ์นธ์ (r, c)๋ก ๋ํ๋ผ ์ ์๊ณ , r์ ๋ถ์ชฝ์ผ๋ก๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์, c๋ ์์ชฝ์ผ๋ก ๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์ ๋ก๋ด ์ฒญ์๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ด ์๋ ํ์ฌ ์์น๋ฅผ ์ฒญ์ํ๋ค. ํ์ฌ ์์น์์ ํ์ฌ ๋ฐฉํฅ์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ๋ฐฉํฅ๋ถํฐ ์ฐจ๋ก๋๋ก ํ์์ ์งํํ๋ค. ์ผ์ชฝ ๋ฐฉํฅ์ ์์ง ์ฒญ์ํ์ง ์์ ๊ณต๊ฐ์ด ์กด์ฌํ๋ค๋ฉด, ๊ทธ ๋ฐฉํฅ์ผ๋ก ํ์ ํ ๋ค์ ํ ์นธ์ ์ ์งํ๊ณ 1๋ฒ๋ถํฐ ์งํํ๋ค. ์ผ์ชฝ ๋ฐฉํฅ์ ์ฒญ์ํ ๊ณต๊ฐ์ด ์๋ค๋ฉด, ๊ทธ ๋ฐฉํฅ์ผ..
์ธ์ฒด์ ์น๋ช ์ ์ธ ๋ฐ์ด๋ฌ์ค๋ฅผ ์ฐ๊ตฌํ๋ ์ฐ๊ตฌ์์์ ๋ฐ์ด๋ฌ์ค๊ฐ ์ ์ถ ๋ฐ์ด๋ฌ์ค๋ ์์ง ํผ์ง์ง ์์๊ณ , ๋ฐ์ด๋ฌ์ค์ ํ์ฐ์ ๋ง๊ธฐ ์ํด์ ์ฐ๊ตฌ์์ ๋ฒฝ์ ์ธ์ฐ๋ ค๊ณ ํ๋ค ์ฐ๊ตฌ์๋ ํฌ๊ธฐ๊ฐ N×M์ธ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, ์ง์ฌ๊ฐํ์ 1×1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ์ผ๋ก ๋๋์ด์ ธ ์๋ค ์ฐ๊ตฌ์๋ ๋น ์นธ, ๋ฒฝ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๋ฒฝ์ ์นธ ํ๋๋ฅผ ๊ฐ๋ ์ฐจ์งํ๋ค. ์ผ๋ถ ์นธ์ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ๋ฉฐ, ์ด ๋ฐ์ด๋ฌ์ค๋ ์ํ์ข์ฐ๋ก ์ธ์ ํ ๋น ์นธ์ผ๋ก ๋ชจ๋ ํผ์ ธ๋๊ฐ ์ ์๋ค. ์๋ก ์ธ์ธ ์ ์๋ ๋ฒฝ์ ๊ฐ์๋ 3๊ฐ์ด๋ฉฐ, ๊ผญ 3๊ฐ๋ฅผ ์ธ์์ผ ํ๋ค. 0์ ๋น ์นธ, 1์ ๋ฒฝ, 2๋ ๋ฐ์ด๋ฌ์ค๊ฐ ์๋ ๊ณณ์ด๋ค. ์๋ฌด๋ฐ ๋ฒฝ์ ์ธ์ฐ์ง ์๋๋ค๋ฉด, ๋ฐ์ด๋ฌ์ค๋ ๋ชจ๋ ๋น ์นธ์ผ๋ก ํผ์ ธ๋๊ฐ ์ ์๋ค. ๋ฒฝ์ 3๊ฐ ์ธ์ด ๋ค, ๋ฐ์ด๋ฌ์ค๊ฐ ํผ์ง ์ ์๋ ๊ณณ์ ์์ ์์ญ ์ฐ๊ตฌ์์ ์ง..
ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํฌ๊ธฐ๊ฐ 1×1์ธ ์ ์ฌ๊ฐํ์ ์ฌ๋ฌ ๊ฐ ์ด์ด์ ๋ถ์ธ ๋ํ ์ ์ฌ๊ฐํ์ ์๋ก ๊ฒน์น๋ฉด ์ ๋๋ค. ๋ํ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ๋ณ๋ผ๋ฆฌ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ฆ, ๊ผญ์ง์ ๊ณผ ๊ผญ์ง์ ๋ง ๋ง๋ฟ์ ์์ผ๋ฉด ์ ๋๋ค. ์ ์ฌ๊ฐํ 4๊ฐ๋ฅผ ์ด์ด ๋ถ์ธ ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํ ํธ๋ก๋ฏธ๋ ธ ์๋ฆ์ด๋ ํฌ๊ธฐ๊ฐ N×M์ธ ์ข ์ด ์์ ํ ํธ๋ก๋ฏธ๋ ธ ํ๋๋ฅผ ๋์ผ๋ ค๊ณ ํ๋ค. ์ข ์ด๋ 1×1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์์ผ๋ฉฐ, ๊ฐ๊ฐ์ ์นธ์๋ ์ ์๊ฐ ํ๋ ์ฐ์ฌ ์๋ค. ํ ํธ๋ก๋ฏธ๋ ธ ํ๋๋ฅผ ์ ์ ํ ๋์์ ํ ํธ๋ก๋ฏธ๋ ธ๊ฐ ๋์ธ ์นธ์ ์ฐ์ฌ ์๋ ์๋ค์ ํฉ์ ์ต๋๋ก ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ํ ํธ๋ก๋ฏธ๋ ธ๋ ๋ฐ๋์ ํ ์ ์ฌ๊ฐํ์ด ์ ํํ ํ๋์ ์นธ์ ํฌํจํ๋๋ก ๋์์ผ ํ๋ฉฐ, ํ์ ์ด๋ ๋์นญ์ ์์ผ๋ ๋๋ค. ์ฒซ์งธ ์ค์ ์ข ์ด์ ์ธ๋ก ํฌ๊ธฐ N๊ณผ ๊ฐ๋ก ํฌ๊ธฐ M์ด ์ฃผ์ด์ง๋ค. (4..
ํฌ๊ธฐ๊ฐ N×M์ธ ์ง๋๊ฐ ์กด์ฌํ๋ค. ์ง๋์ ์ค๋ฅธ์ชฝ์ ๋์ชฝ, ์์ชฝ์ ๋ถ์ชฝ์ด๋ค. ์ด ์ง๋์ ์์ ์ฃผ์ฌ์๊ฐ ํ๋ ๋์ฌ์ ธ ์์ผ๋ฉฐ, ์ง๋์ ์ขํ๋ (r, c)๋ก ๋ํ๋ด๋ฉฐ, r๋ ๋ถ์ชฝ์ผ๋ก๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์, c๋ ์์ชฝ์ผ๋ก๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์ ์ฃผ์ฌ์๋ ์ง๋ ์์ ์ ๋ฉด์ด 1์ด๊ณ , ๋์ชฝ์ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ด 3์ธ ์ํ๋ก ๋์ฌ์ ธ ์์ผ๋ฉฐ, ๋์ฌ์ ธ ์๋ ๊ณณ์ ์ขํ๋ (x, y) ์ด๋ค. ๊ฐ์ฅ ์ฒ์์ ์ฃผ์ฌ์์๋ ๋ชจ๋ ๋ฉด์ 0์ด ์ ํ์ ธ ์๋ค. ์ง๋์ ๊ฐ ์นธ์๋ ์ ์๊ฐ ํ๋์ฉ ์ฐ์ฌ์ ธ ์๋ค. ์ฃผ์ฌ์๋ฅผ ๊ตด๋ ธ์ ๋, ์ด๋ํ ์นธ์ ์ฐ์ฌ ์๋ ์๊ฐ 0์ด๋ฉด, ์ฃผ์ฌ์์ ๋ฐ๋ฅ๋ฉด์ ์ฐ์ฌ ์๋ ์๊ฐ ์นธ์ ๋ณต์ฌ๋๋ค. 0์ด ์๋ ๊ฒฝ์ฐ์๋ ์นธ์ ์ฐ์ฌ ์๋ ์๊ฐ ์ฃผ์ฌ์์ ๋ฐ๋ฅ๋ฉด์ผ๋ก ๋ณต์ฌ๋๋ฉฐ, ์นธ์ ์ฐ์ฌ ์๋ ์๋ 0์ด ๋๋ค. ์ฃผ์ฌ์๋ฅผ ๋์ ๊ณณ์ ์ขํ์ ์ด..
๊ฒ์์๋ ๋ฑ์ด ๋์์ ๊ธฐ์ด๋ค๋๋๋ฐ, ์ฌ๊ณผ๋ฅผ ๋จน์ผ๋ฉด ๋ฑ ๊ธธ์ด๊ฐ ๋์ด๋๋ค. ๋ฑ์ด ์ด๋ฆฌ์ ๋ฆฌ ๊ธฐ์ด๋ค๋๋ค๊ฐ ๋ฒฝ ๋๋ ์๊ธฐ์์ ์ ๋ชธ๊ณผ ๋ถ๋ชํ๋ฉด ๊ฒ์์ด ๋๋๋ค. ๊ฒ์์ NxN ์ ์ฌ๊ฐ ๋ณด๋์์์ ์งํ๋๊ณ , ๋ช๋ช ์นธ์๋ ์ฌ๊ณผ๊ฐ ๋์ฌ์ ธ ์๋ค. ๋ณด๋์ ์ํ์ข์ฐ ๋์ ๋ฒฝ์ด ์๋ค. ๊ฒ์์ด ์์ํ ๋ ๋ฑ์ ๋งจ์ ๋งจ์ข์ธก์ ์์นํ๊ณ ๋ฑ์ ๊ธธ์ด๋ 1 ์ด๋ค. ๋ฑ์ ์ฒ์์ ์ค๋ฅธ์ชฝ์ ํฅํ๋ค. ๋ฑ์ ๋งค ์ด๋ง๋ค ์ด๋์ ํ๋๋ฐ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ ๋ฐ๋ฅธ๋ค. ๋จผ์ ๋ฑ์ ๋ชธ๊ธธ์ด๋ฅผ ๋๋ ค ๋จธ๋ฆฌ๋ฅผ ๋ค์์นธ์ ์์น์ํจ๋ค. ๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๊ทธ ์นธ์ ์๋ ์ฌ๊ณผ๊ฐ ์์ด์ง๊ณ ๊ผฌ๋ฆฌ๋ ์์ง์ด์ง ์๋๋ค. ๋ง์ฝ ์ด๋ํ ์นธ์ ์ฌ๊ณผ๊ฐ ์๋ค๋ฉด, ๋ชธ๊ธธ์ด๋ฅผ ์ค์ฌ์ ๊ผฌ๋ฆฌ๊ฐ ์์นํ ์นธ์ ๋น์์ค๋ค. ์ฆ, ๋ชธ๊ธธ์ด๋ ๋ณํ์ง ์๋๋ค. ์ฌ๊ณผ์ ์์น์ ๋ฑ์ ์ด๋๊ฒฝ๋ก๊ฐ ์ฃผ์ด์ง ๋ ..
ํ ๋ฒ์ ์ด๋์ ๋ณด๋ ์์ ์๋ ์ ์ฒด ๋ธ๋ก์ ์ํ์ข์ฐ ๋ค ๋ฐฉํฅ ์ค ํ๋๋ก ์ด๋์ํค๋ ๊ฒ ๊ฐ์ ๊ฐ์ ๊ฐ๋ ๋ ๋ธ๋ก์ด ์ถฉ๋ํ๋ฉด ๋ ๋ธ๋ก์ ํ๋๋ก ํฉ์ณ์ง๊ฒ ๋๋ค. ํ ๋ฒ์ ์ด๋์์ ์ด๋ฏธ ํฉ์ณ์ง ๋ธ๋ก์ ๋ ๋ค๋ฅธ ๋ธ๋ก๊ณผ ๋ค์ ํฉ์ณ์ง ์ ์๋ค. (์ค์ ๊ฒ์์์๋ ์ด๋์ ํ ๋ฒ ํ ๋๋ง๋ค ๋ธ๋ก์ด ์ถ๊ฐ๋์ง๋ง, ์ด ๋ฌธ์ ์์ ๋ธ๋ก์ด ์ถ๊ฐ๋๋ ๊ฒฝ์ฐ๋ ์๋ค) ๋๊ฐ์ ์๊ฐ ์ธ ๊ฐ๊ฐ ์๋ ๊ฒฝ์ฐ์๋ ์ด๋ํ๋ ค๊ณ ํ๋ ์ชฝ์ ์นธ์ด ๋จผ์ ํฉ์ณ์ง๋ค. ์ด ๋ฌธ์ ์์ ๋ค๋ฃจ๋ 2048 ๊ฒ์์ ๋ณด๋์ ํฌ๊ธฐ๊ฐ N×N ์ด๋ค. ๋ณด๋์ ํฌ๊ธฐ์ ๋ณด๋ํ์ ๋ธ๋ก ์ํ๊ฐ ์ฃผ์ด์ก์ ๋, ์ต๋ 5๋ฒ ์ด๋ํด์ ๋ง๋ค ์ ์๋ ๊ฐ์ฅ ํฐ ๋ธ๋ก์ ๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ฒซ์งธ ์ค์ ๋ณด๋์ ํฌ๊ธฐ N (1 ≤ N ≤ 20)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฒ์ํ์ ์ด..