[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋“ฑ๊ตฃ๊ธธ :: C++, ํšจ์œจ์„ฑ ํ†ต๊ณผํ•˜๊ธฐ, ์ฝ”๋“œ
Algorithm ๋ฌธ์ œ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค 2020. 12. 27. 11:31

๋“ฑ๊ตฃ๊ธธ ๋ฌธ์ œ ๋ฌธ์ œ ์„ค๋ช… ๊ณ„์†๋˜๋Š” ํญ์šฐ๋กœ ์ผ๋ถ€ ์ง€์—ญ์ด ๋ฌผ์— ์ž ๊ฒผ์Šต๋‹ˆ๋‹ค. ๋ฌผ์— ์ž ๊ธฐ์ง€ ์•Š์€ ์ง€์—ญ์„ ํ†ตํ•ด ํ•™๊ต๋ฅผ ๊ฐ€๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ง‘์—์„œ ํ•™๊ต๊นŒ์ง€ ๊ฐ€๋Š” ๊ธธ์€ m x n ํฌ๊ธฐ์˜ ๊ฒฉ์ž๋ชจ์–‘์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ์€ m = 4, n = 3 ์ธ ๊ฒฝ์šฐ์ž…๋‹ˆ๋‹ค. ๊ฐ€์žฅ ์™ผ์ชฝ ์œ„, ์ฆ‰ ์ง‘์ด ์žˆ๋Š” ๊ณณ์˜ ์ขŒํ‘œ๋Š” (1, 1)๋กœ ๋‚˜ํƒ€๋‚ด๊ณ  ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜, ์ฆ‰ ํ•™๊ต๊ฐ€ ์žˆ๋Š” ๊ณณ์˜ ์ขŒํ‘œ๋Š” (m, n)์œผ๋กœ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค. ๊ฒฉ์ž์˜ ํฌ๊ธฐ m, n๊ณผ ๋ฌผ์ด ์ž ๊ธด ์ง€์—ญ์˜ ์ขŒํ‘œ๋ฅผ ๋‹ด์€ 2์ฐจ์› ๋ฐฐ์—ด puddles์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์˜ค๋ฅธ์ชฝ๊ณผ ์•„๋ž˜์ชฝ์œผ๋กœ๋งŒ ์›€์ง์—ฌ ์ง‘์—์„œ ํ•™๊ต๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋‹จ๊ฒฝ๋กœ์˜ ๊ฐœ์ˆ˜๋ฅผ 1,000,000,007๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”. ์ œํ•œ์‚ฌํ•ญ ๊ฒฉ์ž์˜ ํฌ๊ธฐ m, n์€ 1 ..