[python]๋ฐฑ์ค€ 17836๋ฒˆ : ๊ณต์ฃผ๋‹˜์„ ๊ตฌํ•ด๋ผ!
Algorithm ๋ฌธ์ œ/BOJ 2020. 3. 13. 14:42

๊ณต์ฃผ๋‹˜์„ ๊ตฌํ•ด๋ผ! ์‹œ๊ฐ„ ์ œํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ์ œ์ถœ ์ •๋‹ต ๋งž์€ ์‚ฌ๋žŒ ์ •๋‹ต ๋น„์œจ 1 ์ดˆ 256 MB 2397 551 418 22.012% ๋ฌธ์ œ ์šฉ์‚ฌ๋Š” ๋งˆ์™•์ด ์ˆจ๊ฒจ๋†“์€ ๊ณต์ฃผ๋‹˜์„ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด (N, M) ํฌ๊ธฐ์˜ ์„ฑ ์ž…๊ตฌ (1,1)์œผ๋กœ ๋“ค์–ด์™”๋‹ค. ๋งˆ์™•์€ ์šฉ์‚ฌ๊ฐ€ ๊ณต์ฃผ๋ฅผ ์ฐพ์ง€ ๋ชปํ•˜๋„๋ก ์„ฑ์˜ ์—ฌ๋Ÿฌ ๊ตฐ๋ฐ ๋งˆ๋ฒ• ๋ฒฝ์„ ์„ธ์›Œ๋†“์•˜๋‹ค. ์šฉ์‚ฌ๋Š” ํ˜„์žฌ์˜ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ฌด๊ธฐ๋กœ๋Š” ๋งˆ๋ฒ• ๋ฒฝ์„ ํ†ต๊ณผํ•  ์ˆ˜ ์—†์œผ๋ฉฐ, ๋งˆ๋ฒ• ๋ฒฝ์„ ํ”ผํ•ด (N, M) ์œ„์น˜์— ์žˆ๋Š” ๊ณต์ฃผ๋‹˜์„ ๊ตฌ์ถœํ•ด์•ผ๋งŒ ํ•œ๋‹ค. ๋งˆ์™•์€ ์šฉ์‚ฌ๊ฐ€ ๊ดด๋กญํžˆ๊ธฐ ์œ„ํ•ด ๊ณต์ฃผ์—๊ฒŒ ์ €์ฃผ๋ฅผ ๊ฑธ์—ˆ๋‹ค. ์ €์ฃผ์— ๊ฑธ๋ฆฐ ๊ณต์ฃผ๋Š” T์‹œ๊ฐ„ ์ด๋‚ด๋กœ ์šฉ์‚ฌ๋ฅผ ๋งŒ๋‚˜์ง€ ๋ชปํ•œ๋‹ค๋ฉด ์˜์›ํžˆ ๋Œ๋กœ ๋ณ€ํ•˜๊ฒŒ ๋œ๋‹ค. ๊ณต์ฃผ๋‹˜์„ ๊ตฌ์ถœํ•˜๊ณ  ํ”„๋Ÿฌํฌ์ฆˆ๋ฅผ ๋ฐ˜๋“œ์‹œ ํ•˜๊ณ  ์‹ถ์€ ์šฉ์‚ฌ๋Š” T์‹œ๊ฐ„ ๋‚ด์— ๋ฐ˜๋“œ์‹œ ๊ณต์ฃผ๋‹˜์ด ์žˆ๋Š” ๊ณณ์œผ๋กœ ๋„๋‹ฌํ•ด์•ผ ํ•œ๋‹ค. ์šฉ์‚ฌ๋Š” ํ•œ ์นธ์„ ์ด๋™..