๋ฌธ์ ์ค๋ช
๊ณ์๋๋ ํญ์ฐ๋ก ์ผ๋ถ ์ง์ญ์ด ๋ฌผ์ ์ ๊ฒผ์ต๋๋ค. ๋ฌผ์ ์ ๊ธฐ์ง ์์ ์ง์ญ์ ํตํด ํ๊ต๋ฅผ ๊ฐ๋ ค๊ณ ํฉ๋๋ค. ์ง์์ ํ๊ต๊น์ง ๊ฐ๋ ๊ธธ์ m x n ํฌ๊ธฐ์ ๊ฒฉ์๋ชจ์์ผ๋ก ๋ํ๋ผ ์ ์์ต๋๋ค.
์๋ ๊ทธ๋ฆผ์ m = 4, n = 3 ์ธ ๊ฒฝ์ฐ์ ๋๋ค.
![](https://blog.kakaocdn.net/dn/bxwHVL/btrL23DQa3v/cyqddd1GtLiiOwBghpy3t1/img.png)
๊ฐ์ฅ ์ผ์ชฝ ์, ์ฆ ์ง์ด ์๋ ๊ณณ์ ์ขํ๋ (1, 1)๋ก ๋ํ๋ด๊ณ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์๋, ์ฆ ํ๊ต๊ฐ ์๋ ๊ณณ์ ์ขํ๋ (m, n)์ผ๋ก ๋ํ๋ ๋๋ค.
๊ฒฉ์์ ํฌ๊ธฐ m, n๊ณผ ๋ฌผ์ด ์ ๊ธด ์ง์ญ์ ์ขํ๋ฅผ ๋ด์ 2์ฐจ์ ๋ฐฐ์ด puddles์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ์ค๋ฅธ์ชฝ๊ณผ ์๋์ชฝ์ผ๋ก๋ง ์์ง์ฌ ์ง์์ ํ๊ต๊น์ง ๊ฐ ์ ์๋ ์ต๋จ๊ฒฝ๋ก์ ๊ฐ์๋ฅผ 1,000,000,007๋ก ๋๋ ๋๋จธ์ง๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- ๊ฒฉ์์ ํฌ๊ธฐ m, n์ 1 ์ด์ 100 ์ดํ์ธ ์์ฐ์์
๋๋ค.
- m๊ณผ n์ด ๋ชจ๋ 1์ธ ๊ฒฝ์ฐ๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- ๋ฌผ์ ์ ๊ธด ์ง์ญ์ 0๊ฐ ์ด์ 10๊ฐ ์ดํ์ ๋๋ค.
- ์ง๊ณผ ํ๊ต๊ฐ ๋ฌผ์ ์ ๊ธด ๊ฒฝ์ฐ๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
![](https://blog.kakaocdn.net/dn/cM3rTf/btrL1yD2DwD/e0nkW4F21QPmD3B6LYNSPk/img.png)
ํ์ด ์ฝ๋
def solution(m, n, puddles):
answer = 0
dp = [[0 for _ in range(m)] for _ in range(n)]
dp[0][0] = 1
for p in puddles:
a, b = p
dp[b-1][a-1] = -1
for i in range(n):
for j in range(m):
if dp[i][j] == 0:
if i-1 == -1 or (i-1 >= 0 and dp[i-1][j] == -1):
# ์๊ฐ ๋ฒฝ์ด๊ฑฐ๋, ๋ฒฝ์ ์๋๋ฐ ์
๋ฉ์ด์ธ ๊ฒฝ์ฐ
if j-1 == -1 or (j-1 >= 0 and dp[i][j-1] == -1):
continue
else:
dp[i][j] = dp[i][j-1]
elif j-1 == -1 or (j-1 >= 0 and dp[i][j-1] == -1):
# ์ผ์ชฝ์ด ๋ฒฝ์ด๊ฑฐ๋, ๋ฒฝ์ ์๋๋ฐ ์
๋ฉ์ด์ธ ๊ฒฝ์ฐ
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i][j-1] + dp[i-1][j]
return dp[-1][-1] % 1_000_000_007
์ ํ์ ์ธ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ๋ฌธ์ ์ด๋ค.
๋ฌธ์ ์์ ์ฃผ์๊น๊ฒ ๋ณด์์ผ ํ ํน์ฑ์, (1, 1) ์์น์ ๋ฌด์กฐ๊ฑด ์ง์ด ์๊ณ (m, n) ์์น์ ๋ฌด์กฐ๊ฑด ํ๊ต๊ฐ ์๋ค.
์ด๋์ ํ๋ค๋ฉด ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ๊ฑฐ๋, ์๋๋ก ์ด๋ํ๋ ๊ฒฝ์ฐ๋ฐ์ ์๋ค.
๋ฐ๋ผ์ ํ ์นธ์ ๋ํด์ ์ง์ ์ ์ด๋์ ๊ณ ๋ คํ ๋์๋ ์์์ ๋ด๋ ค์๋์ง, ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ์๋์ง๋ฅผ ๊ณ ๋ คํ๋ฉด ๋๋ค.
์ด ๊ทธ๋ฆผ์ ๋ณด๋ฉด ์ดํด๊ฐ ํธํ๋ค.
+ ํ์๊ฐ ๋ ์นธ์, ์ผ์ชฝ์์ ์ด๋ํ๊ฑฐ๋, ์์์ ์ด๋ํ ์ ์๋ ๊ฒฝ์ฐ์ด๋ค.
๋ฐ๋ผ์ dp ๋ฐฐ์ด์ ๋ง๋ค์ด ๋ฉ๋ชจ์ด์ ์ด์ ์ ํด๊ฐ๋ฉฐ ๋ก์ง์ ์์ฑํ๋ฉด ๋๋ค.
์ถ๊ฐ๋ก ์ฝ๋์ ๋์จ ์ฃผ์์ ๋ณด๋ฉด, ์ด๋ป๊ฒ ์๊ฐ์ ํ๋์ง ์ดํดํ๊ธฐ ํธํ ๊ฒ์ด๋ค.
'๐ ์ฝ๋ฉํ ์คํธ ๋๋น : PS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ ๋ฐ๋จน๊ธฐ (level2, python) (0) | 2022.09.13 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] [3์ฐจ] n์ง์ ๊ฒ์ (level2, python) (0) | 2022.09.13 |
[ํ๋ก๊ทธ๋๋จธ์ค] [1์ฐจ] ํ๋ ์ฆ4๋ธ๋ก (level2, python) (1) | 2022.09.13 |
[ํ๋ก๊ทธ๋๋จธ์ค] ํผ๋ก๋ (level2, python) (0) | 2022.09.13 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๋จ์ด ๋ณํ (level3, python) (0) | 2022.09.13 |