[C++/ํ๋ก๊ทธ๋๋จธ์ค] ๊ฒฝ์ฃผ๋ก ๊ฑด์ค (2020 ์นด์นด์ค ์ธํด์ญ)
๋ฌธ์ https://programmers.co.kr/learn/courses/30/lessons/67259 ์ฝ๋ฉํ
์คํธ ์ฐ์ต - ๊ฒฝ์ฃผ๋ก ๊ฑด์ค [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr ๋ฌธ์ ๋ฅผ ์์ฝํ์๋ฉด, ์ ์ฌ๊ฐํ ๋ชจ์์ board์์ (0, 0)์์ (N-1, N-..
2022. 1. 18.
[๋ฐฑ์ค/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..
2021. 4. 14.
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ฑ๊ตฃ๊ธธ
๋ฌธ์ ์ค๋ช
๊ณ์๋๋ ํญ์ฐ๋ก ์ผ๋ถ ์ง์ญ์ด ๋ฌผ์ ์ ๊ฒผ์ต๋๋ค. ๋ฌผ์ ์ ๊ธฐ์ง ์์ ์ง์ญ์ ํตํด ํ๊ต๋ฅผ ๊ฐ๋ ค๊ณ ํฉ๋๋ค. ์ง์์ ํ๊ต๊น์ง ๊ฐ๋ ๊ธธ์ m x n ํฌ๊ธฐ์ ๊ฒฉ์๋ชจ์์ผ๋ก ๋ํ๋ผ ์ ์์ต๋๋ค. ์๋ ๊ทธ๋ฆผ์ m = 4, n = 3 ์ธ ๊ฒฝ์ฐ์
๋๋ค. ๊ฐ์ฅ ์ผ์ชฝ ์, ์ฆ ์ง์ด ์๋ ๊ณณ์ ์ขํ๋ (1, 1)๋ก ๋ํ๋ด๊ณ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์๋, ์ฆ ํ๊ต๊ฐ ์๋ ๊ณณ์ ์ขํ๋ (m, n)์ผ๋ก ๋ํ๋
๋๋ค. ๊ฒฉ์์ ํฌ๊ธฐ m, n๊ณผ ๋ฌผ์ด ์ ๊ธด ์ง์ญ์ ์ขํ๋ฅผ ๋ด์ 2์ฐจ์ ๋ฐฐ์ด puddles์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ์ค๋ฅธ์ชฝ๊ณผ ์๋์ชฝ์ผ๋ก๋ง ์์ง์ฌ ์ง์์ ํ๊ต๊น์ง ๊ฐ ์ ์๋ ์ต๋จ๊ฒฝ๋ก์ ๊ฐ์๋ฅผ 1,000,000,007๋ก ๋๋ ๋๋จธ์ง๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ ๊ฒฉ์์ ํฌ๊ธฐ m, n์ 1 ์ด์ 100 ..
2020. 12. 28.