๋ชฉ๋ก๊ฐ€์žฅ ํฐ ์ •์‚ฌ๊ฐํ˜• (1)

Hello Ocean! ๐ŸŒผ

[๋ฐฑ์ค€/C++] 1915. ๊ฐ€์žฅ ํฐ ์ •์‚ฌ๊ฐํ˜•

๋ฌธ์ œ ๋ฐฐ์—ด์—์„œ 1๋กœ ๋œ ๊ฐ€์žฅ ํฐ ์ •์‚ฌ๊ฐํ˜•์˜ ํฌ๊ธฐ๋ฅผ ๊ตฌํ•ด๋ผ! www.acmicpc.net/problem/1915 1915๋ฒˆ: ๊ฐ€์žฅ ํฐ ์ •์‚ฌ๊ฐํ˜• ์ฒซ์งธ ์ค„์— n, m(1 โ‰ค n, m โ‰ค 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ n๊ฐœ์˜ ์ค„์—๋Š” m๊ฐœ์˜ ์ˆซ์ž๋กœ ๋ฐฐ์—ด์ด ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ํ’€์ด DP๋ฅผ ์ด์šฉํ•˜๊ฒ ๋‹ค! cache[r][c] = min(min(cache[r + 1][c], cache[r + 1][c + 1]), cache[r][c + 1])+1; cache๋ฐฐ์—ด์—์„œ ์ œ์ผ ์•„๋ž˜ ํ–‰, ์˜ค๋ฅธ์ชฝ ์—ด์€ table๊ณผ ๋˜‘๊ฐ™์ด ์ฑ„์›Œ์ค€๋‹ค. ๊ทธ ํ›„์— ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ฉด์„œ, table๊ฐ’์ด 0์ด๋ฉด 0์œผ๋กœ ์ฑ„์šฐ๊ณ  ๋„˜์–ด๊ฐ€๊ณ , 0์ด ์•„๋‹ˆ๋ฉด ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด cache[r + 1][c], cache[r + 1][c + 1], cach..
Algorithm 2021. 4. 14. 12:55
์ด์ „ Prev 1 Next ๋‹ค์Œ