๋ชฉ๋ก์๊ณ ๋ฆฌ์ฆ (74)
๐ป
https://www.acmicpc.net/problem/15685 15685๋ฒ: ๋๋๊ณค ์ปค๋ธ ์ฒซ์งธ ์ค์ ๋๋๊ณค ์ปค๋ธ์ ๊ฐ์ N(1 ≤ N ≤ 20)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋๋๊ณค ์ปค๋ธ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋๋๊ณค ์ปค๋ธ์ ์ ๋ณด๋ ๋ค ์ ์ x, y, d, g๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. x์ y๋ ๋๋๊ณค ์ปค๋ธ์ ์์ ์ , d๋ ์์ ๋ฐฉํฅ, g๋ ์ธ๋์ด๋ค. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๋๋๊ณค ์ปค๋ธ๋ ๊ฒฉ์ ๋ฐ์ผ๋ก ๋ฒ์ด๋์ง ์๋๋ค. ๋๋๊ณค ์ปค๋ธ๋ ์๋ก ๊ฒน์น ์ ์๋ค. ๋ฐฉํฅ์ 0, 1, 2, www.acmicpc.net ๋ฌธ์ ๋๋๊ณค ์ปค๋ธ๋ ๋ค์๊ณผ ๊ฐ์ ์ธ ๊ฐ์ง ์์ฑ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ์ด์ฐจ์ ์ขํ ํ๋ฉด ์์์ ์ ์๋๋ค. ์ขํ ํ๋ฉด์ x์ถ์ → ๋ฐฉํฅ..
๋ฌธ์ ์ค๋์ ์คํํธ๋งํฌ์ ๋ค๋๋ ์ฌ๋๋ค์ด ๋ชจ์ฌ์ ์ถ๊ตฌ๋ฅผ ํด๋ณด๋ ค๊ณ ํ๋ค. ์ถ๊ตฌ๋ ํ์ผ ์คํ์ ํ๊ณ ์๋ฌด ์ฐธ์๋ ์๋๋ค. ์ถ๊ตฌ๋ฅผ ํ๊ธฐ ์ํด ๋ชจ์ธ ์ฌ๋์ ์ด N๋ช ์ด๊ณ ์ ๊ธฐํ๊ฒ๋ N์ ์ง์์ด๋ค. ์ด์ N/2๋ช ์ผ๋ก ์ด๋ฃจ์ด์ง ์คํํธ ํ๊ณผ ๋งํฌ ํ์ผ๋ก ์ฌ๋๋ค์ ๋๋ ์ผ ํ๋ค. BOJ๋ฅผ ์ด์ํ๋ ํ์ฌ ๋ต๊ฒ ์ฌ๋์๊ฒ ๋ฒํธ๋ฅผ 1๋ถํฐ N๊น์ง๋ก ๋ฐฐ์ ํ๊ณ , ์๋์ ๊ฐ์ ๋ฅ๋ ฅ์น๋ฅผ ์กฐ์ฌํ๋ค. ๋ฅ๋ ฅ์น Sij๋ i๋ฒ ์ฌ๋๊ณผ j๋ฒ ์ฌ๋์ด ๊ฐ์ ํ์ ์ํ์ ๋, ํ์ ๋ํด์ง๋ ๋ฅ๋ ฅ์น์ด๋ค. ํ์ ๋ฅ๋ ฅ์น๋ ํ์ ์ํ ๋ชจ๋ ์์ ๋ฅ๋ ฅ์น Sij์ ํฉ์ด๋ค. Sij๋ Sji์ ๋ค๋ฅผ ์๋ ์์ผ๋ฉฐ, i๋ฒ ์ฌ๋๊ณผ j๋ฒ ์ฌ๋์ด ๊ฐ์ ํ์ ์ํ์ ๋, ํ์ ๋ํด์ง๋ ๋ฅ๋ ฅ์น๋ Sij์ Sji์ด๋ค. N=4์ด๊ณ , S๊ฐ ์๋์ ๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ์ดํด๋ณด์. i\j12341..
๋ฌธ์ ์ค๋ช ์คํจ์จ ์ํผ ๊ฒ์ ๊ฐ๋ฐ์ ์ค๋ ๋ฆฌ๋ ํฐ ๊ณ ๋ฏผ์ ๋น ์ก๋ค. ๊ทธ๋ ๊ฐ ๋ง๋ ํ๋์ฆ ์ค์ฒ์ฑ์ด ๋์ฑ๊ณต์ ๊ฑฐ๋์ง๋ง, ์์ฆ ์ ๊ท ์ฌ์ฉ์์ ์๊ฐ ๊ธ๊ฐํ ๊ฒ์ด๋ค. ์์ธ์ ์ ๊ท ์ฌ์ฉ์์ ๊ธฐ์กด ์ฌ์ฉ์ ์ฌ์ด์ ์คํ ์ด์ง ์ฐจ์ด๊ฐ ๋๋ฌด ํฐ ๊ฒ์ด ๋ฌธ์ ์๋ค. ์ด ๋ฌธ์ ๋ฅผ ์ด๋ป๊ฒ ํ ๊น ๊ณ ๋ฏผ ํ ๊ทธ๋ ๋ ๋์ ์ผ๋ก ๊ฒ์ ์๊ฐ์ ๋๋ ค์ ๋์ด๋๋ฅผ ์กฐ์ ํ๊ธฐ๋ก ํ๋ค. ์ญ์ ์ํผ ๊ฐ๋ฐ์๋ผ ๋๋ถ๋ถ์ ๋ก์ง์ ์ฝ๊ฒ ๊ตฌํํ์ง๋ง, ์คํจ์จ์ ๊ตฌํ๋ ๋ถ๋ถ์์ ์๊ธฐ์ ๋น ์ง๊ณ ๋ง์๋ค. ์ค๋ ๋ฆฌ๋ฅผ ์ํด ์คํจ์จ์ ๊ตฌํ๋ ์ฝ๋๋ฅผ ์์ฑํ๋ผ. ์คํจ์จ์ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํ๋ค. ์คํ ์ด์ง์ ๋๋ฌํ์ผ๋ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์ / ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์ ์ ์ฒด ์คํ ์ด์ง์ ๊ฐ์ N, ๊ฒ์์ ์ด์ฉํ๋ ์ฌ์ฉ์๊ฐ ํ์ฌ ๋ฉ์ถฐ์๋ ์คํ ์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ธด ๋ฐฐ์ด stages๊ฐ..
๋ฌธ์ ์ค๋ช ์นด์นด์ค์ ์ ์ ๊ฐ๋ฐ์๋ก ์ ์ฌํ ์ฝ์ ์ ๋ฐฐ ๊ฐ๋ฐ์๋ก๋ถํฐ ๊ฐ๋ฐ์ญ๋ ๊ฐํ๋ฅผ ์ํด ๋ค๋ฅธ ๊ฐ๋ฐ์๊ฐ ์์ฑํ ์์ค ์ฝ๋๋ฅผ ๋ถ์ํ์ฌ ๋ฌธ์ ์ ์ ๋ฐ๊ฒฌํ๊ณ ์์ ํ๋ผ๋ ์ ๋ฌด ๊ณผ์ ๋ฅผ ๋ฐ์์ต๋๋ค. ์์ค๋ฅผ ์ปดํ์ผํ์ฌ ๋ก๊ทธ๋ฅผ ๋ณด๋ ๋๋ถ๋ถ ์์ค ์ฝ๋ ๋ด ์์ฑ๋ ๊ดํธ๊ฐ ๊ฐ์๋ ๋ง์ง๋ง ์ง์ด ๋ง์ง ์์ ํํ๋ก ์์ฑ๋์ด ์ค๋ฅ๊ฐ ๋๋ ๊ฒ์ ์๊ฒ ๋์์ต๋๋ค. ์์ ํด์ผ ํ ์์ค ํ์ผ์ด ๋๋ฌด ๋ง์์ ๊ณ ๋ฏผํ๋ ์ฝ์ ์์ค ์ฝ๋์ ์์ฑ๋ ๋ชจ๋ ๊ดํธ๋ฅผ ๋ฝ์์ ์ฌ๋ฐ๋ฅธ ์์๋๋ก ๋ฐฐ์น๋ ๊ดํธ ๋ฌธ์์ด์ ์๋ ค์ฃผ๋ ํ๋ก๊ทธ๋จ์ ๋ค์๊ณผ ๊ฐ์ด ๊ฐ๋ฐํ๋ ค๊ณ ํฉ๋๋ค. ์ฉ์ด์ ์ ์ '(' ์ ')' ๋ก๋ง ์ด๋ฃจ์ด์ง ๋ฌธ์์ด์ด ์์ ๊ฒฝ์ฐ, '(' ์ ๊ฐ์์ ')' ์ ๊ฐ์๊ฐ ๊ฐ๋ค๋ฉด ์ด๋ฅผ ๊ท ํ์กํ ๊ดํธ ๋ฌธ์์ด์ด๋ผ๊ณ ๋ถ๋ฆ ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ฌ๊ธฐ์ '('์ ')'์ ๊ดํธ์ ์ง๋ ๋ชจ๋..
๋ฌธ์ ์ค๋ช ์คํ์ด๋ค์ ๋งค์ผ ๋ค๋ฅธ ์ท์ ์กฐํฉํ์ฌ ์ ์ด ์์ ์ ์์ฅํฉ๋๋ค. ์๋ฅผ ๋ค์ด ์คํ์ด๊ฐ ๊ฐ์ง ์ท์ด ์๋์ ๊ฐ๊ณ ์ค๋ ์คํ์ด๊ฐ ๋๊ทธ๋ ์๊ฒฝ, ๊ธด ์ฝํธ, ํ๋์ ํฐ์ ์ธ ๋ฅผ ์ ์๋ค๋ฉด ๋ค์๋ ์ ์ฒญ๋ฐ์ง๋ฅผ ์ถ๊ฐ๋ก ์ ๊ฑฐ๋ ๋๊ทธ๋ ์๊ฒฝ ๋์ ๊ฒ์ ์ ๊ธ๋ผ์ค๋ฅผ ์ฐฉ์ฉํ๊ฑฐ๋ ํด์ผ ํฉ๋๋ค. ์ข ๋ฅ์ด๋ฆ ์ผ๊ตด ๋๊ทธ๋ ์๊ฒฝ, ๊ฒ์ ์ ๊ธ๋ผ์ค ์์ ํ๋์ ํฐ์ ์ธ ํ์ ์ฒญ๋ฐ์ง ๊ฒ์ท ๊ธด ์ฝํธ ์คํ์ด๊ฐ ๊ฐ์ง ์์๋ค์ด ๋ด๊ธด 2์ฐจ์ ๋ฐฐ์ด clothes๊ฐ ์ฃผ์ด์ง ๋ ์๋ก ๋ค๋ฅธ ์ท์ ์กฐํฉ์ ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ clothes์ ๊ฐ ํ์ [์์์ ์ด๋ฆ, ์์์ ์ข ๋ฅ]๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. ์คํ์ด๊ฐ ๊ฐ์ง ์์์ ์๋ 1๊ฐ ์ด์ 30๊ฐ ์ดํ์ ๋๋ค. ๊ฐ์ ์ด๋ฆ์ ๊ฐ์ง ์์์ ์กด์ฌํ์ง ์์ต๋๋ค. clothe..
๋ฌธ์ ์ธ์ฒด์ ์น๋ช ์ ์ธ ๋ฐ์ด๋ฌ์ค๋ฅผ ์ฐ๊ตฌํ๋ ์ฐ๊ตฌ์์์ ๋ฐ์ด๋ฌ์ค๊ฐ ์ ์ถ๋์๋ค. ๋คํํ ๋ฐ์ด๋ฌ์ค๋ ์์ง ํผ์ง์ง ์์๊ณ , ๋ฐ์ด๋ฌ์ค์ ํ์ฐ์ ๋ง๊ธฐ ์ํด์ ์ฐ๊ตฌ์์ ๋ฒฝ์ ์ธ์ฐ๋ ค๊ณ ํ๋ค. ์ฐ๊ตฌ์๋ ํฌ๊ธฐ๊ฐ N×M์ธ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, ์ง์ฌ๊ฐํ์ 1×1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ์ฐ๊ตฌ์๋ ๋น ์นธ, ๋ฒฝ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๋ฒฝ์ ์นธ ํ๋๋ฅผ ๊ฐ๋ ์ฐจ์งํ๋ค. ์ผ๋ถ ์นธ์ ๋ฐ์ด๋ฌ์ค๊ฐ ์กด์ฌํ๋ฉฐ, ์ด ๋ฐ์ด๋ฌ์ค๋ ์ํ์ข์ฐ๋ก ์ธ์ ํ ๋น ์นธ์ผ๋ก ๋ชจ๋ ํผ์ ธ๋๊ฐ ์ ์๋ค. ์๋ก ์ธ์ธ ์ ์๋ ๋ฒฝ์ ๊ฐ์๋ 3๊ฐ์ด๋ฉฐ, ๊ผญ 3๊ฐ๋ฅผ ์ธ์์ผ ํ๋ค. ์๋ฅผ ๋ค์ด, ์๋์ ๊ฐ์ด ์ฐ๊ตฌ์๊ฐ ์๊ธด ๊ฒฝ์ฐ๋ฅผ ์ดํด๋ณด์. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 ..
๋ฌธ์ ๊น์ง์์ด ๋ฃ๋ ๋ชปํ ์ฌ๋์ ๋ช ๋จ๊ณผ, ๋ณด๋ ๋ชปํ ์ฌ๋์ ๋ช ๋จ์ด ์ฃผ์ด์ง ๋, ๋ฃ๋ ๋ณด๋ ๋ชปํ ์ฌ๋์ ๋ช ๋จ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๋ฃ๋ ๋ชปํ ์ฌ๋์ ์ N, ๋ณด๋ ๋ชปํ ์ฌ๋์ ์ M์ด ์ฃผ์ด์ง๋ค. ์ด์ด์ ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๊ฑธ์ณ ๋ฃ๋ ๋ชปํ ์ฌ๋์ ์ด๋ฆ๊ณผ, N+2์งธ ์ค๋ถํฐ ๋ณด๋ ๋ชปํ ์ฌ๋์ ์ด๋ฆ์ด ์์๋๋ก ์ฃผ์ด์ง๋ค. ์ด๋ฆ์ ๋์ด์ฐ๊ธฐ ์์ด ์์ด ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ง๋ฉฐ, ๊ทธ ๊ธธ์ด๋ 20 ์ดํ์ด๋ค. N, M์ 500,000 ์ดํ์ ์์ฐ์์ด๋ค. ์ถ๋ ฅ ๋ฃ๋ณด์ก์ ์์ ๊ทธ ๋ช ๋จ์ ์ฌ์ ์์ผ๋ก ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ1 3 4 ohhenrie charlie baesangwook obama baesangwook ohhenrie clinton ์์ ์ถ๋ ฅ1 2 baesangwook ohhenrie ์๊ฐ ..
๋ฌธ์ 0๊ณผ 1๋ก๋ง ์ด๋ฃจ์ด์ง ์๋ฅผ ์ด์ง์๋ผ ํ๋ค. ์ด๋ฌํ ์ด์ง์ ์ค ํน๋ณํ ์ฑ์ง์ ๊ฐ๋ ๊ฒ๋ค์ด ์๋๋ฐ, ์ด๋ค์ ์ด์น์(pinary number)๋ผ ํ๋ค. ์ด์น์๋ ๋ค์์ ์ฑ์ง์ ๋ง์กฑํ๋ค. ์ด์น์๋ 0์ผ๋ก ์์ํ์ง ์๋๋ค. ์ด์น์์์๋ 1์ด ๋ ๋ฒ ์ฐ์์ผ๋ก ๋ํ๋์ง ์๋๋ค. ์ฆ, 11์ ๋ถ๋ถ ๋ฌธ์์ด๋ก ๊ฐ์ง ์๋๋ค. ์๋ฅผ ๋ค๋ฉด 1, 10, 100, 101, 1000, 1001 ๋ฑ์ด ์ด์น์๊ฐ ๋๋ค. ํ์ง๋ง 0010101์ด๋ 101101์ ๊ฐ๊ฐ 1, 2๋ฒ ๊ท์น์ ์๋ฐฐ๋๋ฏ๋ก ์ด์น์๊ฐ ์๋๋ค. N(1 ≤ N ≤ 90)์ด ์ฃผ์ด์ก์ ๋, N์๋ฆฌ ์ด์น์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ N์๋ฆฌ ์ด์น์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ1 3 ์์ ์ถ๋ ฅ1 2 ์๊ฐ n = 1 ..