๋ชฉ๋ก๐ฆฅ ์ฝํ /BAEKJOON (287)
๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
์ด๋ค ๋ฐ์ ์๋ ํ์๋ค์ ์์ผ์ด ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๋์ด๊ฐ ์ ์ ์ฌ๋๊ณผ ๊ฐ์ฅ ๋ง์ ์ฌ๋์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๋ฐ์ ์๋ ํ์์ ์ n์ด ์ฃผ์ด์ง๋ค. (1 ≤ n ≤ 100) ๋ค์ n๊ฐ ์ค์๋ ๊ฐ ํ์์ ์ด๋ฆ๊ณผ ์์ผ์ด "์ด๋ฆ dd mm yyyy"์ ๊ฐ์ ํ์ ์ด๋ฆ์ ๊ทธ ํ์์ ์ด๋ฆ์ด๋ฉฐ, ์ต๋ 15๊ธ์๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. dd mm yyyy๋ ์์ผ ์ผ, ์, ์ฐ๋์ด๋ค.(1990 ≤ yyyy ≤ 2010, 1 ≤ mm ≤ 12, 1 ≤ dd ≤ 31) ์ฃผ์ด์ง๋ ์์ผ์ ์ฌ๋ฐ๋ฅธ ๋ ์ง์ด๋ฉฐ, ์ฐ, ์ ์ผ์ 0์ผ๋ก ์์ํ์ง ์๋๋ค. ์ด๋ฆ์ด ๊ฐ๊ฑฐ๋, ์์ผ์ด ๊ฐ์ ์ฌ๋์ ์๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๊ฐ์ฅ ๋์ด๊ฐ ์ ์ ์ฌ๋์ ์ด๋ฆ, ๋์งธ ์ค์ ๊ฐ์ฅ ๋์ด๊ฐ ๋ง์ ์ฌ๋ ์ด๋ฆ์ ์ถ๋ ฅ // [5635] ์์ผ /* ์ด๋ค ๋ฐ์ ์..
๊ตฌ๋จ์ด ์ฑ์ ์ ๋ด์ง ๋ชปํ๋ค๋ฉด ๋ต์ ์ ์ ์ ์์ ๋ฟ ์ฒผ์๊ฐ ๋ฆฌ์คํธ์์ ๊ฐ์ฅ ๋น์ผ ์ ์๋ฅผ ์ฐพ์๋ผ ์ ์๋๋ก ๋๊ธฐ ์ ๋ ฅ ์ฒซ ๋ฒ์งธ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ n์ด ์ฃผ์ด์ง๋ค (n≤100) ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ ๋ฒ์งธ ์ค p๋ ๊ณ ๋ คํด์ผ๋ ์ ์์ ์์ด๋ค (1≤p≤100). ๊ทธ ์๋ p๊ฐ์ ์ค์๋ ์ ์์ ์ ๋ณด๊ฐ ํ์๋๋ค ๊ฐ๊ฐ์ ์ค์ ์ ์์ ๊ฐ๊ฒฉ C ์ ์ด๋ฆ์ ์ ๋ ฅํ๋ค ์ถ๋ ฅ ๊ฐ๊ฐ์ ํ ์คํธ ์ผ์ด์ค์์ ๊ฐ์ฅ ๋น์ผ ์ ์์ ์ด๋ฆ์ ์ถ๋ ฅ // [11098] ์ฒผ์๋ฅผ ๋์์ค /* ๊ตฌ๋จ์ด ์ฑ์ ์ ๋ด์ง ๋ชปํ๋ค๋ฉด ๋ต์ ์ ์ ์ ์์ ๋ฟ ์ฒผ์๊ฐ ๋ฆฌ์คํธ์์ ๊ฐ์ฅ ๋น์ผ ์ ์๋ฅผ ์ฐพ์๋ผ ์ ์๋๋ก ๋๊ธฐ ์ ๋ ฅ ์ฒซ ๋ฒ์งธ ์ค์๋ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ n์ด ์ฃผ์ด์ง๋ค (n≤100) ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ ๋ฒ์งธ ์ค p๋ ๊ณ ๋ คํด์ผ๋ ์ ์์ ์์ด๋ค (1≤p≤1..
M๊ณผ N์ด ์ฃผ์ด์ง ๋ M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์ ์ ๊ณฑ์์ธ ๊ฒ์ ๋ชจ๋ ๊ณจ๋ผ ๊ทธ ํฉ์ ๊ตฌํ๊ณ ๊ทธ ์ค ์ต์๊ฐ์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ ๋ ฅ ์ฒซ์งธ ์ค์ M์ด, ๋์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. M๊ณผ N์ 10000์ดํ์ ์์ฐ์์ด๋ฉฐ M์ N๋ณด๋ค ๊ฐ๊ฑฐ๋ ์๋ค. ์ถ๋ ฅ M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์ ์ ๊ณฑ์์ธ ๊ฒ์ ๋ชจ๋ ์ฐพ์ ์ฒซ์งธ ์ค์ ๊ทธ ํฉ์, ๋์งธ ์ค์ ๊ทธ ์ค ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค. M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์ ์ ๊ณฑ์๊ฐ ์์ ๊ฒฝ์ฐ ์ฒซ์งธ ์ค์ -1 ์ถ๋ ฅ // [1977] ์์ ์ ๊ณฑ์ /* M๊ณผ N์ด ์ฃผ์ด์ง ๋ M์ด์ N์ดํ์ ์์ฐ์ ์ค ์์ ์ ๊ณฑ์์ธ ๊ฒ์ ๋ชจ๋ ๊ณจ๋ผ ๊ทธ ํฉ์ ๊ตฌํ๊ณ ๊ทธ ์ค ์ต์๊ฐ์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑ ์ ๋ ฅ ์ฒซ์งธ ์ค์ M์ด, ๋์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. M๊ณผ N์ 10000์ดํ์ ์์ฐ์์ด๋ฉฐ M์ N๋ณด๋ค ๊ฐ๊ฑฐ๋ ์๋ค..
์ ๋ ฅ ๋ฐ์ ๋๋ก ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ ๋ ฅ์ด ์ฃผ์ด์ง๋ค. ์ ๋ ฅ์ ์ต๋ 100์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ์ํ๋ฒณ ์๋ฌธ์, ๋๋ฌธ์, ๊ณต๋ฐฑ, ์ซ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ์ค์ 100๊ธ์๋ฅผ ๋์ง ์์ผ๋ฉฐ, ๋น ์ค์ ์ฃผ์ด์ง์ง ์๋๋ค. ๋, ๊ฐ ์ค์ ๊ณต๋ฐฑ์ผ๋ก ์์ํ์ง ์๊ณ , ๊ณต๋ฐฑ์ผ๋ก ๋๋์ง ์๋๋ค. ์ถ๋ ฅ ์ ๋ ฅ๋ฐ์ ๊ทธ๋๋ก ์ถ๋ ฅํ๋ค. // [11718] ๊ทธ๋๋ก ์ถ๋ ฅํ๊ธฐ /* ์ ๋ ฅ ์ ๋ ฅ์ด ์ฃผ์ด์ง๋ค. ์ ๋ ฅ์ ์ต๋ 100์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ์ํ๋ฒณ ์๋ฌธ์, ๋๋ฌธ์, ๊ณต๋ฐฑ, ์ซ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ์ค์ 100๊ธ์๋ฅผ ๋์ง ์์ผ๋ฉฐ, ๋น ์ค์ ์ฃผ์ด์ง์ง ์๋๋ค. ๋, ๊ฐ ์ค์ ๊ณต๋ฐฑ์ผ๋ก ์์ํ์ง ์๊ณ , ๊ณต๋ฐฑ์ผ๋ก ๋๋์ง ์๋๋ค. ์ถ๋ ฅ ์ ๋ ฅ๋ฐ์ ๊ทธ๋๋ก ์ถ๋ ฅํ๋ค. */ #include #include using namespace..
์ํ ๋๋ฆฌ๊ธฐ ๋ฐ์ง๋ฆ์ด 1, 2, ..., N์ธ ์ํ์ด ํฌ๊ธฐ๊ฐ ์์์ง๋ ์์ผ๋ก ๋ฐ๋ฅ์ ๋์ฌ์๊ณ ์ํ์ ์ค์ฌ์ ๋ชจ๋ ๊ฐ๋ค ์ํ์ ๋ฐ์ง๋ฆ์ด i์ด๋ฉด, ๊ทธ ์ํ์ i๋ฒ์งธ ์ํ ๊ฐ๊ฐ์ ์ํ์๋ M๊ฐ์ ์ ์๊ฐ ์ ํ์๊ณ , i๋ฒ์งธ ์ํ์ ์ ํ j๋ฒ์งธ ์์ ์์น๋ (i, j) ์์ ์์น (i, 1)์ (i, 2), (i, M)๊ณผ ์ธ์ (i, M)์ (i, M-1), (i, 1)๊ณผ ์ธ์ (i, j)๋ (i, j-1), (i, j+1)๊ณผ ์ธ์ (2 ≤ j ≤ M-1) (1, j)๋ (2, j)์ ์ธ์ (N, j)๋ (N-1, j)์ ์ธ์ (i, j)๋ (i-1, j), (i+1, j)์ ์ธ์ (2 ≤ i ≤ N-1) ์ํ์ ํ์ ์ ๋ ๋ฆฝ์ ์ผ๋ก ์ด๋ฃจ์ด์ง๋ค 2๋ฒ ์ํ์ ํ์ ํ์ ๋, ๋๋จธ์ง ์ํ์ ํ์ ํ์ง ์๋๋ค ์ํ์ ํ์ ์ํฌ ..
๊ตฌ์ฌํ์ถ ๊ตฌ์ฌ ํ์ถ์ ์ง์ฌ๊ฐํ ๋ณด๋์ ๋นจ๊ฐ ๊ตฌ์ฌ๊ณผ ํ๋ ๊ตฌ์ฌ์ ํ๋์ฉ ๋ฃ์ ๋ค์, ๋นจ๊ฐ ๊ตฌ์ฌ์ ๊ตฌ๋ฉ์ ํตํด ๋นผ๋ด๋ ๊ฒ์ ๋ณด๋์ ์ธ๋ก ํฌ๊ธฐ๋ N, ๊ฐ๋ก ํฌ๊ธฐ๋ M, 1×1ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์๋ค ๊ฐ์ฅ ๋ฐ๊นฅ ํ๊ณผ ์ด์ ๋ชจ๋ ๋งํ์ ธ ์๊ณ , ๋ณด๋์๋ ๊ตฌ๋ฉ์ด ํ๋ ๋นจ๊ฐ ๊ตฌ์ฌ๊ณผ ํ๋ ๊ตฌ์ฌ์ ํฌ๊ธฐ๋ ๋ณด๋์์ 1×1ํฌ๊ธฐ์ ์นธ์ ๊ฐ๋ ์ฑ์ฐ๋ ์ฌ์ด์ฆ์ด๊ณ , ๊ฐ๊ฐ ํ๋์ฉ ๋ค์ด๊ฐ ์๋ค ๋นจ๊ฐ ๊ตฌ์ฌ์ ๊ตฌ๋ฉ์ ํตํด์ ๋นผ๋ด๋ ๊ฒ์ด๋ค ์ด๋, ํ๋ ๊ตฌ์ฌ์ด ๊ตฌ๋ฉ์ ๋ค์ด๊ฐ๋ฉด ์ ๋๋ค ๊ตฌ์ฌ์ ์์ผ๋ก ๊ฑด๋๋ฆด ์๋ ์๊ณ , ์ค๋ ฅ์ ์ด์ฉํด์ ์ด๋ฆฌ ์ ๋ฆฌ ๊ตด๋ ค์ผ ํ๋ค ์ผ์ชฝ์ผ๋ก ๊ธฐ์ธ์ด๊ธฐ, ์ค๋ฅธ์ชฝ์ผ๋ก ๊ธฐ์ธ์ด๊ธฐ, ์์ชฝ์ผ๋ก ๊ธฐ์ธ์ด๊ธฐ, ์๋์ชฝ์ผ๋ก ๊ธฐ์ธ์ด๊ธฐ์ ๊ฐ์ ๋ค ๊ฐ์ง ๋์ ๊ฐ๊ฐ์ ๋์์์ ๊ณต์ ๋์์ ์์ง์ธ๋ค ๋นจ๊ฐ ๊ตฌ์ฌ์ด ๊ตฌ๋ฉ์ ๋น ์ง๋ฉด ์ฑ๊ณต์ด์ง๋ง, ํ๋ ..
์์ด ์คํ๊ต ์์ด ์คํ๊ต์ ์ฝ๋ฉ ๋์๋ฆฌ์์ ๊ฒ์์ ๋ง๋ค์๋ค ์ด ๊ฒ์์ ํฌ๊ธฐ๊ฐ N×N์ธ ๊ฒฉ์์์ ์งํ๋๊ณ , ์ด๊ธฐ์ ๊ฒฉ์์ ๋ชจ๋ ์นธ์๋ ๋ธ๋ก์ด ํ๋์ฉ ๋ค์ด์์ ๋ธ๋ก์ ๊ฒ์์ ๋ธ๋ก, ๋ฌด์ง๊ฐ ๋ธ๋ก, ์ผ๋ฐ ๋ธ๋ก ์ผ๋ฐ ๋ธ๋ก์ M๊ฐ์ง ์์์ด ์๊ณ , ์์ M์ดํ์ ์์ฐ์๋ก ํํ ๊ฒ์์ ๋ธ๋ก์ -1 ๋ฌด์ง๊ฐ ๋ธ๋ก์ 0์ผ๋ก ํํ (i, j)๋ ๊ฒฉ์์ i๋ฒ ํ, j๋ฒ ์ด์ ์๋ฏธ |r1 - r2| + |c1 - c2| = 1์ ๋ง์กฑํ๋ ๋ ์นธ (r1, c1)๊ณผ (r2, c2)๋ฅผ ์ธ์ ํ ์นธ ๋ธ๋ก ๊ทธ๋ฃน์ ์ฐ๊ฒฐ๋ ๋ธ๋ก์ ์งํฉ ์ผ๋ฐ ๋ธ๋ก์ด ์ ์ด๋ ํ๋ ์์ด์ผ ํ๋ฉฐ, ์ผ๋ฐ ๋ธ๋ก์ ์์ ๋ชจ๋ ๊ฐ์์ผ ํ๋ค ๊ฒ์์ ๋ธ๋ก์ ํฌํจ๋๋ฉด ์ ๋๊ณ , ๋ฌด์ง๊ฐ ๋ธ๋ก์ ์ผ๋ง๋ ๋ค์ด์๋ ์๊ด์๋ค ๊ทธ๋ฃน์ ์ํ ๋ธ๋ก์ ๊ฐ์๋ 2๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์์ผ ํ๋ฉฐ, ์์์..
์์ด์ด๋ฑํ๊ต ์์ด ์ด๋ฑํ๊ต์๋ ๊ต์ค์ด ํ๋ ์๊ณ , ๊ต์ค์ N×N ํฌ๊ธฐ์ ๊ฒฉ์ ํ๊ต์ ๋ค๋๋ ํ์์ ์๋ N2๋ช ๋ชจ๋ ํ์์ ์๋ฆฌ๋ฅผ ์ ํ๋ ๋ ํ์์ 1๋ฒ๋ถํฐ N2๋ฒ๊น์ง ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์๊ณ , (r, c)๋ rํ c์ด์ ์๋ฏธ ๊ต์ค์ ๊ฐ์ฅ ์ผ์ชฝ ์ ์นธ์ (1, 1)์ด๊ณ , ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์๋ซ ์นธ์ (N, N) ์ ์๋์ ํ์์ ์์๋ฅผ ์ ํ๊ณ , ๊ฐ ํ์์ด ์ข์ํ๋ ํ์ 4๋ช ๋ ๋ชจ๋ ์กฐ์ฌ ๊ท์น์ ์ด์ฉํด ์ ํด์ง ์์๋๋ก ํ์์ ์๋ฆฌ๋ฅผ ์ ํ๊ธฐ ํ ์นธ์๋ ํ์ ํ ๋ช ์ ์๋ฆฌ๋ง ์์ ์ ์๊ณ , r1 - r2| + |c1 - c2| = 1์ ๋ง์กฑํ๋ ๋ ์นธ์ด (r1, c1)๊ณผ (r2, c2)๋ฅผ ์ธ์ ํ๋ค 1) ๋น์ด์๋ ์นธ ์ค์์ ์ข์ํ๋ ํ์์ด ์ธ์ ํ ์นธ์ ๊ฐ์ฅ ๋ง์ ์นธ์ผ๋ก ์๋ฆฌ๋ฅผ ์ ํ๋ค 2) 1์ ๋ง์กฑํ๋ ์นธ์ด ์ฌ๋ฌ ๊ฐ์ด๋ฉด, ..