๋ชฉ๋ก์๊ณ ๋ฆฌ์ฆ/๋ฌธ์ ํ์ด Baekjoon (61)
๐ป
๋ฌธ์ ์ธ์ฒด์ ์น๋ช ์ ์ธ ๋ฐ์ด๋ฌ์ค๋ฅผ ์ฐ๊ตฌํ๋ ์ฐ๊ตฌ์์์ ๋ฐ์ด๋ฌ์ค๊ฐ ์ ์ถ๋์๋ค. ๋คํํ ๋ฐ์ด๋ฌ์ค๋ ์์ง ํผ์ง์ง ์์๊ณ , ๋ฐ์ด๋ฌ์ค์ ํ์ฐ์ ๋ง๊ธฐ ์ํด์ ์ฐ๊ตฌ์์ ๋ฒฝ์ ์ธ์ฐ๋ ค๊ณ ํ๋ค. ์ฐ๊ตฌ์๋ ํฌ๊ธฐ๊ฐ 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 ..
๋ฌธ์ ์ต๊ทผ์ ๊ฐ๋ฐ๋ ์ง๋ฅํ ๊ธฐ์ฐจ๊ฐ 1๋ฒ์ญ(์ถ๋ฐ์ญ)๋ถํฐ 4๋ฒ์ญ(์ข ์ฐฉ์ญ)๊น์ง 4๊ฐ์ ์ ์ฐจ์ญ์ด ์๋ ๋ ธ์ ์์ ์ดํ๋๊ณ ์๋ค. ์ด ๊ธฐ์ฐจ์๋ ํ๊ฑฐ๋ ๋ด๋ฆฌ๋ ์ฌ๋ ์๋ฅผ ์๋์ผ๋ก ์ธ์ํ ์ ์๋ ์ฅ์น๊ฐ ์๋ค. ์ด ์ฅ์น๋ฅผ ์ด์ฉํ์ฌ ์ถ๋ฐ์ญ์์ ์ข ์ฐฉ์ญ๊น์ง ๊ฐ๋ ๋์ค ๊ธฐ์ฐจ ์์ ์ฌ๋์ด ๊ฐ์ฅ ๋ง์ ๋์ ์ฌ๋ ์๋ฅผ ๊ณ์ฐํ๋ ค๊ณ ํ๋ค. ๋จ, ์ด ๊ธฐ์ฐจ๋ฅผ ์ด์ฉํ๋ ์ฌ๋๋ค์ ์ง์ ์์์ด ํฌ์ฒ ํ์ฌ, ์ญ์์ ๊ธฐ์ฐจ์ ํ ๋, ๋ด๋ฆด ์ฌ๋์ด ๋ชจ๋ ๋ด๋ฆฐ ํ์ ๊ธฐ์ฐจ์ ํ๋ค๊ณ ๊ฐ์ ํ๋ค. ๋ด๋ฆฐ ์ฌ๋ ์ํ ์ฌ๋ ์1๋ฒ์ญ(์ถ๋ฐ์ญ)2๋ฒ์ญ3๋ฒ์ญ4๋ฒ์ญ(์ข ์ฐฉ์ญ) 0 32 3 13 28 25 39 0 ์๋ฅผ ๋ค์ด, ์์ ๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ์ดํด๋ณด์. ์ด ๊ฒฝ์ฐ, ๊ธฐ์ฐจ ์์ ์ฌ๋์ด ๊ฐ์ฅ ๋ง์ ๋๋ 2๋ฒ์ญ์์ 3๋ช ์ ์ฌ๋์ด ๊ธฐ์ฐจ์์ ๋ด๋ฆฌ๊ณ , 13๋ช ์ ์ฌ๋์ด ๊ธฐ์ฐจ์ ํ์ ๋๋ก, ..
๋ฌธ์ ์์ฆ ๋ฏผ๊ท๋ค ๋๋ค์์๋ ์คํํธ๋งํฌ์์ ๋ง๋ PS์นด๋๋ฅผ ๋ชจ์ผ๋ ๊ฒ์ด ์ ํ์ด๋ค. PS์นด๋๋ PS(Problem Solving)๋ถ์ผ์์ ์ ๋ช ํ ์ฌ๋๋ค์ ์์ด๋์ ์ผ๊ตด์ด ์ ํ์๋ ์นด๋์ด๋ค. ๊ฐ๊ฐ์ ์นด๋์๋ ๋ฑ๊ธ์ ๋ํ๋ด๋ ์์ด ์น ํด์ ธ ์๊ณ , ๋ค์๊ณผ ๊ฐ์ด 8๊ฐ์ง๊ฐ ์๋ค. ์ ์ค์นด๋ ๋ ๋์นด๋ ์ค๋ ์ง์นด๋ ํผํ์นด๋ ๋ธ๋ฃจ์นด๋ ์ฒญ๋ก์นด๋ ๊ทธ๋ฆฐ์นด๋ ๊ทธ๋ ์ด์นด๋ ์นด๋๋ ์นด๋ํฉ์ ํํ๋ก๋ง ๊ตฌ๋งคํ ์ ์๊ณ , ์นด๋ํฉ์ ์ข ๋ฅ๋ ์นด๋ 1๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ, ์นด๋ 2๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ, ... ์นด๋ N๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ๊ณผ ๊ฐ์ด ์ด N๊ฐ์ง๊ฐ ์กด์ฌํ๋ค. ๋ฏผ๊ท๋ ์นด๋์ ๊ฐ์๊ฐ ์ ์ ํฉ์ด๋๋ผ๋ ๊ฐ๊ฒฉ์ด ๋น์ธ๋ฉด ๋์ ๋ฑ๊ธ์ ์นด๋๊ฐ ๋ง์ด ๋ค์ด์์ ๊ฒ์ด๋ผ๋ ๋ฏธ์ ์ ๋ฏฟ๊ณ ์๋ค. ๋ฐ๋ผ์, ๋ฏผ๊ท๋ ๋์ ์ต๋ํ ๋ง์ด ์ง๋ถํด์ ์นด๋ N๊ฐ ๊ตฌ๋งคํ๋ ค๊ณ ํ๋ค. ์นด..
๋ฌธ์ ๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์ฃผ์ด์ก์ ๋, ์ฒญ์ํ๋ ์์ญ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ก๋ด ์ฒญ์๊ธฐ๊ฐ ์๋ ์ฅ์๋ N×M ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ผ๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, 1×1ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค. ๊ฐ๊ฐ์ ์นธ์ ๋ฒฝ ๋๋ ๋น ์นธ์ด๋ค. ์ฒญ์๊ธฐ๋ ๋ฐ๋ผ๋ณด๋ ๋ฐฉํฅ์ด ์์ผ๋ฉฐ, ์ด ๋ฐฉํฅ์ ๋, ์, ๋จ, ๋ถ์ค ํ๋์ด๋ค. ์ง๋์ ๊ฐ ์นธ์ (r, c)๋ก ๋ํ๋ผ ์ ์๊ณ , r์ ๋ถ์ชฝ์ผ๋ก๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์, c๋ ์์ชฝ์ผ๋ก ๋ถํฐ ๋จ์ด์ง ์นธ์ ๊ฐ์์ด๋ค. ๋ก๋ด ์ฒญ์๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ด ์๋ํ๋ค. ํ์ฌ ์์น๋ฅผ ์ฒญ์ํ๋ค. ํ์ฌ ์์น์์ ํ์ฌ ๋ฐฉํฅ์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ๋ฐฉํฅ๋ถํฐ ์ฐจ๋ก๋๋ก ํ์์ ์งํํ๋ค. ์ผ์ชฝ ๋ฐฉํฅ์ ์์ง ์ฒญ์ํ์ง ์์ ๊ณต๊ฐ์ด ์กด์ฌํ๋ค๋ฉด, ๊ทธ ๋ฐฉํฅ์ผ๋ก ํ์ ํ ๋ค์ ํ ์นธ์ ์ ์งํ๊ณ 1๋ฒ๋ถํฐ ์งํํ๋ค. ์ผ์ชฝ ๋ฐฉํฅ์ ์ฒญ์..
๋ฌธ์ ํ๊ทธ ์๋ฆฌํ ์ด๋ ๊ตฌ๋ฉ์ด ๋ซ๋ ค์๋ ์ด์ฐจ์ ๊ฒ์ํ์์ ํ๋ ๊ฒ์์ด๋ค. ๊ฐ ๊ตฌ๋ฉ์๋ ํ์ ํ๋ ๊ฝ์ ์ ์๋ค. ํ์ ์ํ, ์์ง ๋ฐฉํฅ์ผ๋ก ์ธ์ ํ ํ์ ๋ฐ์ด๋์ด์ ๊ทธ ํ์ ๋ค์ ์นธ์ผ๋ก ์ด๋ํ๋ ๊ฒ๋ง ํ์ฉ๋๋ค. ์ธ์ ํ ํ์ ๋ค์ ์นธ์ ๋น์ด์์ด์ผ ํ๊ณ ๊ทธ ์ธ์ ํ ํ์ ์ ๊ฑฐ๋๋ค. ํ์ฌ ๊ฒ์ํ์ ๊ฝํ์๋ ํ์ ์ํ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋, ํ์ ์ ์ ํ ์์ง์ฌ์ ๊ฒ์ํ์ ๋จ์์๋ ํ์ ๊ฐ์๋ฅผ ์ต์๋ก ํ๋ ค๊ณ ํ๋ค. ๋, ๊ทธ๋ ๊ฒ ๋จ๊ธฐ๊ธฐ ์ํด ํ์ํ ์ต์ ์ด๋ํ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ 1 ≤ N ≤ 100์ด ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ๊ฒ์ํ์ ์ด๊ธฐ ์ํ์ด๋ค. ๊ฒ์ํ์ ๋ชจ๋ ๊ฐ์ ๋ชจ์์ ๊ฐ์ง๋ค. (์์ ์ฐธ๊ณ ) '.'๋ ๋น ์นธ, 'o'๋ ํ์ด ๊ฝํ์๋ ์นธ, '#'๋ ๊ตฌ๋ฉ์ด ์๋..
๋ฌธ์ ์๊ทผ์ด๊ฐ 1ํ๋ ๋, ๋ง์ , ๋บ์ ์ ๋งค์ฐ ์ข์ํ๋ค. ์๊ทผ์ด๋ ์ซ์๊ฐ ์ค ์ง์ด์๋ ๊ฒ์ ๋ณด๊ธฐ๋ง ํ๋ฉด, ๋ง์ง๋ง ๋ ์ซ์ ์ฌ์ด์ '='์ ๋ฃ๊ณ , ๋๋จธ์ง ์ซ์ ์ฌ์ด์๋ '+' ๋๋ '-'๋ฅผ ๋ฃ์ด ๋ฑ์์ ๋ง๋ค๋ฉฐ ๋๊ณ ์๋ค. ์๋ฅผ ๋ค์ด, "8 3 2 4 8 7 2 4 0 8 8"์์ ๋ฑ์ "8+3-2-4+8-7-2-4-0+8=8"์ ๋ง๋ค ์ ์๋ค. ์๊ทผ์ด๋ ์ฌ๋ฐ๋ฅธ ๋ฑ์์ ๋ง๋ค๋ ค๊ณ ํ๋ค. ์๊ทผ์ด๋ ์์ง ํ๊ต์์ ์์๋ฅผ ๋ฐฐ์ฐ์ง ์์๊ณ , 20์ ๋๋ ์๋ ๋ชจ๋ฅธ๋ค. ๋ฐ๋ผ์, ์ผ์ชฝ๋ถํฐ ๊ณ์ฐํ ๋, ์ค๊ฐ์ ๋์ค๋ ์๊ฐ ๋ชจ๋ 0 ์ด์ 20 ์ดํ์ด์ด์ผ ํ๋ค. ์๋ฅผ ๋ค์ด, "8+3+2-4-8-7+2+4+0+8=8"์ ์ฌ๋ฐ๋ฅธ ๋ฑ์์ด์ง๋ง, 8+3+2-4-8-7์ด ์์์ด๊ธฐ ๋๋ฌธ์, ์๊ทผ์ด๊ฐ ๋ง๋ค ์ ์๋ ๋ฑ์์ด๋ค. ์ซ์๊ฐ ์ฃผ์ด์ก์..