๐ช [ํ ํธ๋ก๋ฏธ๋ ธ]
14500๋ฒ: ํ ํธ๋ก๋ฏธ๋ ธ
ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํฌ๊ธฐ๊ฐ 1×1์ธ ์ ์ฌ๊ฐํ์ ์ฌ๋ฌ ๊ฐ ์ด์ด์ ๋ถ์ธ ๋ํ์ด๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ์๋ก ๊ฒน์น๋ฉด ์ ๋๋ค. ๋ํ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ๋ณ
www.acmicpc.net
๐ ๋ฌธ์ ์ค๋ช
ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํฌ๊ธฐ๊ฐ 1×1์ธ ์ ์ฌ๊ฐํ์ ์ฌ๋ฌ ๊ฐ ์ด์ด์ ๋ถ์ธ ๋ํ์ด๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ๋ค.
- ์ ์ฌ๊ฐํ์ ์๋ก ๊ฒน์น๋ฉด ์ ๋๋ค.
- ๋ํ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค.
- ์ ์ฌ๊ฐํ์ ๋ณ๋ผ๋ฆฌ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ฆ, ๊ผญ์ง์ ๊ณผ ๊ผญ์ง์ ๋ง ๋ง๋ฟ์ ์์ผ๋ฉด ์ ๋๋ค.
์ ์ฌ๊ฐํ 4๊ฐ๋ฅผ ์ด์ด ๋ถ์ธ ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํ ํธ๋ก๋ฏธ๋ ธ๋ผ๊ณ ํ๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ 5๊ฐ์ง๊ฐ ์๋ค.

์๋ฆ์ด๋ ํฌ๊ธฐ๊ฐ N×M์ธ ์ข ์ด ์์ ํ ํธ๋ก๋ฏธ๋ ธ ํ๋๋ฅผ ๋์ผ๋ ค๊ณ ํ๋ค. ์ข ์ด๋ 1×1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋์ด์ ธ ์์ผ๋ฉฐ, ๊ฐ๊ฐ์ ์นธ์๋ ์ ์๊ฐ ํ๋ ์ฐ์ฌ ์๋ค.
ํ ํธ๋ก๋ฏธ๋ ธ ํ๋๋ฅผ ์ ์ ํ ๋์์ ํ ํธ๋ก๋ฏธ๋ ธ๊ฐ ๋์ธ ์นธ์ ์ฐ์ฌ ์๋ ์๋ค์ ํฉ์ ์ต๋๋ก ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋จ, ํ ํธ๋ก๋ฏธ๋ ธ๋ ๋ฐ๋์ ํ ์ ์ฌ๊ฐํ์ด ์ ํํ ํ๋์ ์นธ์ ํฌํจํ๋๋ก ๋์์ผ ํ๋ฉฐ, ํ์ ์ด๋ ๋์นญ์ ์์ผ๋ ๋๋ค.
๐๐จ ์ ์ถ๋ ฅ ๋ฐ์ดํฐ
[์ ๋ ฅ]
์ฒซ์งธ ์ค์ ์ข ์ด์ ์ธ๋ก ํฌ๊ธฐ N๊ณผ ๊ฐ๋ก ํฌ๊ธฐ M์ด ์ฃผ์ด์ง๋ค. (4 ≤ N, M ≤ 500)
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ์ข ์ด์ ์ฐ์ฌ ์๋ ์๊ฐ ์ฃผ์ด์ง๋ค. i๋ฒ์งธ ์ค์ j๋ฒ์งธ ์๋ ์์์๋ถํฐ i๋ฒ์งธ ์นธ, ์ผ์ชฝ์์๋ถํฐ j๋ฒ์งธ ์นธ์ ์ฐ์ฌ ์๋ ์์ด๋ค. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ์๋ 1,000์ ๋์ง ์๋ ์์ฐ์์ด๋ค.
5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1
[์ถ๋ ฅ]
์ฒซ์งธ ์ค์ ํ ํธ๋ก๋ฏธ๋ ธ๊ฐ ๋์ธ ์นธ์ ์ฐ์ธ ์๋ค์ ํฉ์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
19
๐ ๋ฌธ์ ํ์ด
ํด๋น ๋ฌธ์ ์ ๊ฒฝ์ฐ, 5๊ฐ์ง ๋ชจ์ ๊ทธ๋ฆฌ๊ณ ๊ฐ ๋ชจ์์ ๋ํ ๋ชจ๋ ํ์ ํ ๋ชจ์๋ค์ ์ด ๊ฒฝ์ฐ์ ์๋ ์๋์ ๊ฐ์ด 19๊ฐ์ง์ด๋ค.

19๊ฐ์ง์ ๊ฒฝ์ฐ์ ์ ไธญ ์ค๋ณต๋๋ ๊ฒฝ์ฐ๋ ์์ผ๋ฏ๋ก ํด๋น ๊ฒฝ์ฐ๋ฅผ ์ ๋ถ ํด๋ณผ ์ ๋ฐ์ ์๊ธฐ์ ์ด๋ '๋ธ๋ฃจํธํฌ์ค' ๋ฌธ์ ์ด๋ค. ๋ชจ๋ ๋ชจ์์ ๊ฐ๊ฐ ํน์ ๊ธฐ์ค์ ์ ์ก์์ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ์ปค๋ฒํ๋ ์ฝ๋๋ฅผ ์์ฑํด๋ณด์.
๐ ํ์ด/๊ฐ๋ ์ ๋ฆฌ
- ๊ฐ๋
: ๋ด์ฉ
'Algorithm > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| [๋ฐฑ์ค] 1463. 1๋ก ๋ง๋ค๊ธฐ (0) | 2022.03.07 |
|---|---|
| [๋ฐฑ์ค] 6064. ์นด์ ๋ฌ๋ ฅ (0) | 2022.03.05 |
| [๋ฐฑ์ค] 1107. ๋ฆฌ๋ชจ์ปจ (0) | 2022.03.01 |
| [๋ฐฑ์ค] 1476. ๋ ์ง ๊ณ์ฐ (0) | 2022.03.01 |
| [๋ฐฑ์ค] 3085. ์ฌํ ๊ฒ์ (0) | 2022.02.23 |