[programmers] ๋ฑ๊ตฃ๊ธธ - Java
ํญ์ฐ๋ก ๋ฌผ์ ์ ๊ธด ์ง์ญ์ ํผํ์ฌ ํ๊ต์ ๊ฐ๋ ์ต๋จ ๊ฒฝ๋ก์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ๋ก, ์ฃผ์ด์ง ๊ฒฉ์์์ ์ค๋ฅธ์ชฝ๊ณผ ์๋์ชฝ์ผ๋ก๋ง ์ด๋ํ ์ ์๋ค. ๋์ ๊ณํ๋ฒ์ ์ฌ์ฉํ์ฌ ๊ฒฝ๋ก ์๋ฅผ ๊ณ์ฐํ๋ฉฐ, ๋ฌผ์ ์ ๊ธด ์ง์ญ์ -1๋ก ํ์ํ์ฌ ๊ฒฝ๋ก ๊ณ์ฐ์์ ์ ์ธํ๋ค. ์ต์ข
๊ฒฐ๊ณผ๋ ๊ฒฉ์์ ์ค๋ฅธ์ชฝ ํ๋จ ๋ชจ์๋ฆฌ์ ์์นํ ๊ฐ์ผ๋ก, ์๊ฐ ๋ณต์ก๋๋ O(mรn)์ด๋ค.
Oct 29, 2024
๋ฑ๊ตฃ๊ธธ
๋ฌธ์ ์ค๋ช
๊ณ์๋๋ ํญ์ฐ๋ก ์ผ๋ถ ์ง์ญ์ด ๋ฌผ์ ์ ๊ฒผ์ต๋๋ค. ๋ฌผ์ ์ ๊ธฐ์ง ์์ ์ง์ญ์ ํตํด ํ๊ต๋ฅผ ๊ฐ๋ ค๊ณ ํฉ๋๋ค. ์ง์์ ํ๊ต๊น์ง ๊ฐ๋ ๊ธธ์ 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 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
- m๊ณผ n์ด ๋ชจ๋ 1์ธ ๊ฒฝ์ฐ๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
- ๋ฌผ์ ์ ๊ธด ์ง์ญ์ 0๊ฐ ์ด์ 10๊ฐ ์ดํ์ ๋๋ค.
- ์ง๊ณผ ํ๊ต๊ฐ ๋ฌผ์ ์ ๊ธด ๊ฒฝ์ฐ๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
m | n | puddles | return |
4 | 3 | [[2, 2]] | 4 |
์ ์ถ๋ ฅ ์ ์ค๋ช
solution.java
class Solution { public int solution(int m, int n, int[][] puddles) { // ์์ ์ ์ final int MOD = 1_000_000_007; // ๊ฒฉ์ ์ด๊ธฐํ int[][] dp = new int[m + 1][n + 1]; // ๋ฌผ์ ์ ๊ธด ์ง์ญ์ -1๋ก ํ์ for (int[] puddle : puddles) { dp[puddle[0]][puddle[1]] = -1; } // (1,1)๋ถํฐ ๊ฒฉ์ ์์ dp[1][1] = 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // ์์ ์ ๊ณผ ๋ฌผ์ ์ ๊ธด ์ง์ญ ๊ฑด๋๋ฐ๊ธฐ if ((i == 1 && j == 1) || dp[i][j] == -1) continue; // ํ์ฌ ์ ์ ๋ํ ๋ฐฉ๋ฒ ์ ๊ณ์ฐ int fromAbove = (i > 1 && dp[i - 1][j] != -1) ? dp[i - 1][j] : 0; int fromLeft = (j > 1 && dp[i][j - 1] != -1) ? dp[i][j - 1] : 0; dp[i][j] = (fromAbove + fromLeft) % MOD; System.out.println("dp["+i+"]["+j+"] = "+dp[i][j]); } } // ๊ฒฐ๊ณผ๋ ๊ฒฉ์์ ์ค๋ฅธ์ชฝ ํ๋จ ๋ชจ์๋ฆฌ์ ์๋ ๊ฐ return dp[m][n]; } }
ํต์ฌ ํค์๋
- ์ค๋ฅธ์ชฝ๊ณผ ์๋์ชฝ์ผ๋ก๋ง ์์ง์ผ ์ ์์ผ๋ฏ๋ก ์ข์ธก ์ ์์์ ๊ฐ๋ฅํ ๊ฒฝ๋ก ๊ฐ์์ ์์ชฝ ์ ์์์ ๊ฐ๋ฅํ ๊ฒฝ๋ก ๊ฐ์๋ฅผ ํฉ์น๋ฉด ํ์ฌ ์ ์ ๊ฒฝ๋ก ๊ฐ์๋ฅผ ๊ตฌํ ์ ์๋ค.
- ์ด ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋๋ ๊ฐ ์ ์ ํ๋ฒ์ฉ ๋ฐ๋ณตํ๋ฏ๋ก ๋ค์๊ณผ ๊ฐ๋ค.
๊ฒฐ๋ก !
๋์ ๊ณํ๋ฒ์ ์์ฉํ๋ ๋ฐฉ๋ฒ์ ๊ณ ๋ฏผํด๋ณผ ์ ์์ด์ ์ข์๋ค.
Share article