๋ฏธ๋กํ์ ๐ช N×Mํฌ๊ธฐ์ ๋ฐฐ์ด๋ก ํํ๋๋ ๋ฏธ๋ก๊ฐ ์๋ค. ๋ฏธ๋ก์์ 1์ ์ด๋ํ ์ ์๋ ์นธ์ ๋ํ๋ด๊ณ , 0์ ์ด๋ํ ์ ์๋ ์นธ์ ๋ํ๋ธ๋ค. ์ด๋ฌํ ๋ฏธ๋ก๊ฐ ์ฃผ์ด์ก์ ๋, (1, 1)์์ ์ถ๋ฐํ์ฌ (N, M)์ ์์น๋ก ์ด๋ํ ๋ ์ง๋์ผ ํ๋ ์ต์์ ์นธ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ํ ์นธ์์ ๋ค๋ฅธ ์นธ์ผ๋ก ์ด๋ํ ๋, ์๋ก ์ธ์ ํ ์นธ์ผ๋ก๋ง ์ด๋ํ ์ ์๋ค. ์์ ์์์๋ 15์นธ์ ์ง๋์ผ (N, M)์ ์์น๋ก ์ด๋ํ ์ ์๋ค. ์นธ์ ์
๋์๋ ์์ ์์น์ ๋์ฐฉ ์์น๋ ํฌํจํ๋ค. ์
๋ ฅ ์ฒซ์งธ ์ค์ ๋ ์ ์ N, M(2 ≤ N, M ≤ 100)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ M๊ฐ์ ์ ์๋ก ๋ฏธ๋ก๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ๊ฐ์ ์๋ค์ ๋ถ์ด์ ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ง๋์ผ ํ๋ ์ต์์ ์นธ ์๋ฅผ ์ถ๋ ฅํ๋ค. ํญ์ ๋..
Algorithm/๐ ๋ฌธ์
๊ทธ๋ฆผ ๐ช ์ด๋ค ํฐ ๋ํ์ง์ ๊ทธ๋ฆผ์ด ๊ทธ๋ ค์ ธ ์์ ๋, ๊ทธ ๊ทธ๋ฆผ์ ๊ฐ์์, ๊ทธ ๊ทธ๋ฆผ ์ค ๋์ด๊ฐ ๊ฐ์ฅ ๋์ ๊ฒ์ ๋์ด๋ฅผ ์ถ๋ ฅํ์ฌ๋ผ. ๋จ, ๊ทธ๋ฆผ์ด๋ผ๋ ๊ฒ์ 1๋ก ์ฐ๊ฒฐ๋ ๊ฒ์ ํ ๊ทธ๋ฆผ์ด๋ผ๊ณ ์ ์ํ์. ๊ฐ๋ก๋ ์ธ๋ก๋ก ์ฐ๊ฒฐ๋ ๊ฒ์ ์ฐ๊ฒฐ์ด ๋ ๊ฒ์ด๊ณ ๋๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ์ด ๋ ๊ฒ์ ๋จ์ด์ง ๊ทธ๋ฆผ์ด๋ค. ๊ทธ๋ฆผ์ ๋์ด๋ ๊ทธ๋ฆผ์ ํฌํจ๋ 1์ ๊ฐ์์ด๋ค. ์
๋ ฅ ์ฒซ์งธ ์ค์ ๋ํ์ง์ ์ธ๋ก ํฌ๊ธฐ n(1 ≤ n ≤ 500)๊ณผ ๊ฐ๋ก ํฌ๊ธฐ m(1 ≤ m ≤ 500)์ด ์ฐจ๋ก๋ก ์ฃผ์ด์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ n+1 ์ค ๊น์ง ๊ทธ๋ฆผ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. (๋จ ๊ทธ๋ฆผ์ ์ ๋ณด๋ 0๊ณผ 1์ด ๊ณต๋ฐฑ์ ๋๊ณ ์ฃผ์ด์ง๋ฉฐ, 0์ ์์น ์ด ์๋ ๋ถ๋ถ, 1์ ์์น ์ด ๋ ๋ถ๋ถ์ ์๋ฏธํ๋ค) ์ถ๋ ฅ ์ฒซ์งธ ์ค์๋ ๊ทธ๋ฆผ์ ๊ฐ์, ๋์งธ ์ค์๋ ๊ทธ ์ค ๊ฐ์ฅ ๋์ ๊ทธ๋ฆผ์ ๋์ด๋ฅผ ์ถ๋ ฅํ์ฌ๋ผ. ๋จ, ..
์ง๊ฒ๋ค๋ฆฌ๊ฑด๋๊ธฐ ์นด์นด์ค ์ด๋ฑํ๊ต์ "๋๋์ฆ ์น๊ตฌ๋ค"์ด "๋ผ์ด์ธ" ์ ์๋๊ณผ ํจ๊ป ๊ฐ์ ์ํ์ ๊ฐ๋ ์ค์ ์ง๊ฒ๋ค๋ฆฌ๊ฐ ์๋ ๊ฐ์ธ์ ๋ง๋์ ๊ฑด๋ํธ์ผ๋ก ๊ฑด๋๋ ค๊ณ ํฉ๋๋ค. "๋ผ์ด์ธ" ์ ์๋์ "๋๋์ฆ ์น๊ตฌ๋ค"์ด ๋ฌด์ฌํ ์ง๊ฒ๋ค๋ฆฌ๋ฅผ ๊ฑด๋ ์ ์๋๋ก ๋ค์๊ณผ ๊ฐ์ด ๊ท์น์ ๋ง๋ค์์ต๋๋ค. ์ง๊ฒ๋ค๋ฆฌ๋ ์ผ๋ ฌ๋ก ๋์ฌ ์๊ณ ๊ฐ ์ง๊ฒ๋ค๋ฆฌ์ ๋๋ค๋์๋ ๋ชจ๋ ์ซ์๊ฐ ์ ํ ์์ผ๋ฉฐ ๋๋ค๋์ ์ซ์๋ ํ ๋ฒ ๋ฐ์ ๋๋ง๋ค 1์ฉ ์ค์ด๋ญ๋๋ค. ๋๋ค๋์ ์ซ์๊ฐ 0์ด ๋๋ฉด ๋ ์ด์ ๋ฐ์ ์ ์์ผ๋ฉฐ ์ด๋๋ ๊ทธ ๋ค์ ๋๋ค๋๋ก ํ๋ฒ์ ์ฌ๋ฌ ์นธ์ ๊ฑด๋ ๋ธ ์ ์์ต๋๋ค. ๋จ, ๋ค์์ผ๋ก ๋ฐ์ ์ ์๋ ๋๋ค๋์ด ์ฌ๋ฌ ๊ฐ์ธ ๊ฒฝ์ฐ ๋ฌด์กฐ๊ฑด ๊ฐ์ฅ ๊ฐ๊น์ด ๋๋ค๋๋ก๋ง ๊ฑด๋๋ธ ์ ์์ต๋๋ค. "๋๋์ฆ ์น๊ตฌ๋ค"์ ๊ฐ์ธ์ ์ผ์ชฝ์ ์์ผ๋ฉฐ, ๊ฐ์ธ์ ์ค๋ฅธ์ชฝ ๊ฑด๋ํธ์ ๋์ฐฉํด์ผ ์ง๊ฒ๋ค๋ฆฌ๋ฅผ ๊ฑด๋..
ํฐ๋ฆฐ๋๋กฌ? (๋ฌธ์ _ 10942) ๋ช
์ฐ๋ ํ์ค์ด์ ํจ๊ป ํฐ๋ฆฐ๋๋กฌ ๋์ด๋ฅผ ํด๋ณด๋ ค๊ณ ํ๋ค. ๋จผ์ , ํ์ค์ด๋ ์์ฐ์ N๊ฐ๋ฅผ ์น ํ์ ์ ๋๋ค. ๊ทธ ๋ค์, ๋ช
์ฐ์๊ฒ ์ง๋ฌธ์ ์ด M๋ฒ ํ๋ค. ๊ฐ ์ง๋ฌธ์ ๋ ์ ์ S์ E(1 ≤ S ≤ E ≤ N)๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, S๋ฒ์งธ ์๋ถํฐ E๋ฒ์งธ ๊น์ง ์๊ฐ ํฐ๋ฆฐ๋๋กฌ์ ์ด๋ฃจ๋์ง๋ฅผ ๋ฌผ์ด๋ณด๋ฉฐ, ๋ช
์ฐ๋ ๊ฐ ์ง๋ฌธ์ ๋ํด ํฐ๋ฆฐ๋๋กฌ์ด๋ค ๋๋ ์๋๋ค๋ฅผ ๋งํด์ผ ํ๋ค. ์๋ฅผ ๋ค์ด, ํ์ค์ด๊ฐ ์น ํ์ ์ ์ ์๊ฐ 1, 2, 1, 3, 1, 2, 1๋ผ๊ณ ํ์. S = 1, E = 3์ธ ๊ฒฝ์ฐ 1, 2, 1์ ํฐ๋ฆฐ๋๋กฌ์ด๋ค. S = 2, E = 5์ธ ๊ฒฝ์ฐ 2, 1, 3, 1์ ํฐ๋ฆฐ๋๋กฌ์ด ์๋๋ค. S = 3, E = 3์ธ ๊ฒฝ์ฐ 1์ ํฐ๋ฆฐ๋๋กฌ์ด๋ค. S = 5, E = 7์ธ ๊ฒฝ์ฐ 1, 2, 1์ ํฐ๋ฆฐ๋๋กฌ์ด๋ค. ์..
ํ์ ์ด๋ฐฅ (๋ฌธ์ _ 15961) ํ์ ์ด๋ฐฅ ์์์ ์๋ ํ์ ํ๋ ๋ฒจํธ ์์ ์ฌ๋ฌ ๊ฐ์ง ์ข
๋ฅ์ ์ด๋ฐฅ์ด ์ ์์ ๋ด๊ฒจ ๋์ฌ ์๊ณ , ์๋์ ์ด ์ค์์ ์๊ธฐ๊ฐ ์ข์ํ๋ ์ด๋ฐฅ์ ๊ณจ๋ผ์ ๋จน๋๋ค. ์ด๋ฐฅ์ ์ข
๋ฅ๋ฅผ ๋ฒํธ๋ก ํํํ ๋, ๋ค์ ๊ทธ๋ฆผ์ ํ์ ์ด๋ฐฅ ์์์ ์ ๋ฒจํธ ์ํ์ ์๋ฅผ ๋ณด์ฌ์ฃผ๊ณ ์๋ค. ๋ฒจํธ ์์๋ ๊ฐ์ ์ข
๋ฅ์ ์ด๋ฐฅ์ด ๋ ์ด์ ์์ ์ ์๋ค. ์๋ก ๋ฌธ์ ์ฐ ํ์ ์ด๋ฐฅ ์์์ ์ด ๋ถ๊ฒฝ๊ธฐ๋ก ์์
์ด ์ด๋ ค์์, ๋ค์๊ณผ ๊ฐ์ด ๋ ๊ฐ์ง ํ์ฌ๋ฅผ ํตํด์ ๋งค์์ ์ฌ๋ฆฌ๊ณ ์ ํ๋ค. ์๋ ํ์ ์ด๋ฐฅ์ ์๋์ด ๋ง์๋๋ก ์ด๋ฐฅ์ ๊ณ ๋ฅด๊ณ , ๋จน์ ์ด๋ฐฅ๋งํผ ์๋๋ฅผ ๊ณ์ฐํ์ง๋ง, ๋ฒจํธ์ ์์์ ํ ์์น๋ถํฐ k๊ฐ์ ์ ์๋ฅผ ์ฐ์ํด์ ๋จน์ ๊ฒฝ์ฐ ํ ์ธ๋ ์ ์ก ๊ฐ๊ฒฉ์ผ๋ก ์ ๊ณตํ๋ค. ๊ฐ ๊ณ ๊ฐ์๊ฒ ์ด๋ฐฅ์ ์ข
๋ฅ ํ๋๊ฐ ์ฐ์ธ ์ฟ ํฐ์ ๋ฐํํ๊ณ , 1๋ฒ ํ์ฌ์ ์ฐธ๊ฐํ ๊ฒฝ..