๋์ ๊ณํ๋ฒ (Dynamic Programming) : ๋ฑ๊ตฃ๊ธธ
๋ฌธ์ ์ถ์ฒ - ํ๋ก๊ทธ๋๋จธ์ค ์ฝ๋ฉํ ์คํธ ๊ณ ๋์ Kit
๋ฌธ์ ์ค๋ช
๊ณ์๋๋ ํญ์ฐ๋ก ์ผ๋ถ ์ง์ญ์ด ๋ฌผ์ ์ ๊ฒผ์ต๋๋ค. ๋ฌผ์ ์ ๊ธฐ์ง ์์ ์ง์ญ์ ํตํด ํ๊ต๋ฅผ ๊ฐ๋ ค๊ณ ํฉ๋๋ค. ์ง์์ ํ๊ต๊น์ง ๊ฐ๋ ๊ธธ์ 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๊ฐ ์ดํ์ ๋๋ค.
- ์ง๊ณผ ํ๊ต๊ฐ ๋ฌผ์ ์ ๊ธด ๊ฒฝ์ฐ๋ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง์ง ์์ต๋๋ค.
์ด์ฉ์ง ๋ฌธ์ ๊ฐ x,y ์ขํ๋ ๊ฑฐ๊พธ๋ก ๋์ด์๊ณ ๋๋จธ์ง๋ฅผ ๊ตฌํ๋ผ๋ ๊ทธ๋ฐ ๋๋ฝ๊ณ ๋ณต์กํ ๋ฌธ์ ์๋๋ฐ,
์ ๋ช ๋๊ธฐ๋ก ์ ๋ช ํ ๋ฌธ์ ์๋ค.
๊ทผ๋ฐ ์ง์ง ๊ทธ๋ด๋งํจ
๋ ๋ฐ๋ก ์์์ฑ๊ธด ํ๋๋ฐ ์ขํ x,y ๋ฐ๋์ธ๊ฑฐ ๋ชฐ๋๋ ์ฌ๋๋ค์ ํ์ฐธ ์ฝ์งํ๋ค๊ฐ ํ์์ํ ๊ณ
๋ง์ ํ์ด์ ์ ๋ต์ ๋ง์๋, ํจ์จ์ฑ ํ ์คํธ์์ 0์ ์ด ๋์์ ํค๋งจ ์ฌ๋๋ค๋ ๋ง๋ค
๋น์ ๋ง ๊ทธ๋ฌ๋๊ฒ ์๋๋ ์์ฌํ์ธ์! ๋ผ๋ ์๋ฏธ์ ๋๋ค
๋๋ ํจ์จ์ฑ ๋๋ฌธ์ ํต๊ณผ๋ฅผ ๋ชปํ์๋๋ฐ, ์ผ๋จ ๋ฌด์กฐ๊ฑด dp๋ก ํ์ด์ผ ํ๊ณ (์ ํํ๋ ๋ชจ๋ฆ)
dp๊ฐ์ ๊ตฌํ ๋ ๋ง๋ค % 1000000007๋ฅผ ํด์ฃผ๋ฉด ํต๊ณผํ๋๋ผ..ใ ใ
์กฐ๊ฑด ๋ฐ์ง๊ฒ ๋ง์์ ๊น๋ค๋ก์ ๋ค.
1. (1,1)์ ํญ์ 1์ด๋ค.
2.(1,y) ์ ์์ชฝ ๊ฐ ๊ทธ๋๋ก, (x,1)์ ์ผ์ชฝ ๊ฐ์ ๊ทธ๋๋ก ๊ฐ์ ธ์์ผ ํจ. ์ด๊ฑฐ ์ ๋๋ก ์ฒ๋ฆฌ ์ํ๋ฉด (1,2)(2,1)์ ๋ฌผ์ ๋ฉ์ด๊ฐ ์์ ๋ ์๋ ๋ต์ 0์ด ๋์์ผ ํ์ง๋ง, ๋ค๋ฅธ ๊ฒฐ๊ณผ๊ฐ์ด ๋์ค๋ ๋ถ์์ฌ๊ฐ ์๊ธด๋ค
3. ์ฐ๋ฆฌ PS ์์์ผ๋ก๋ (n,m)์ด ํ๊ณผ ์ด์ด๊ธฐ ๋๋ฌธ์... ์ด ๋ฌธ์ ์์๋ (m,n)์ผ๋ก ํ์ด์ผํจ
4. ๊ธฐ๋ณธ ํ ์คํธ์ผ์ด์ค๊ฐ ๊ตฌ๋ ค์ ์ง๋ฌธํ๊ธฐ ๊ฒ์ํ์์ ์ถ๊ฐ๋ก ์ฐพ์๋ณด๋๊ฑฐ ์ถ์ฒ
์ฌ๋ฌ๊ฐ์ง๋ก ๋์ ๋ฌธ์ ์๋ค;;
๋์ ํ์ด
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int solution(int m, int n, vector<vector<int>> puddles) {
int answer = 0;
int dp[102][102]={{0,}};
dp[0][0] = 1;
dp[1][1] = 1; dp[1][2] = 1; dp[2][1] = 1;
for(int i=0; i<puddles.size(); ++i){
dp[puddles[i][0]][puddles[i][1]] = -1;
}
for(int j=1; j<=m; ++j){
for(int i=1; i<=n; ++i){
if(i==1&&j==1) continue;
if(dp[j][i]==-1){
dp[j][i] = 0;
continue;
}
if(i==1){
dp[j][i] = dp[j-1][i];
continue;
}
if(j==1){
dp[j][i] = dp[j][i-1];
continue;
}
dp[j][i] = (dp[j-1][i] + dp[j][i-1])% 1000000007;
}
cout<<"\n";
}
answer = dp[m][n];
return answer;
}
'๐ ์๊ณ ๋ฆฌ์ฆ > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/PGS] Lv.3 : ๋จ์ด ๋ณํ (DFS/BFS/๋ฐฑํธ๋ํน) - ์์ ํ์ (0) | 2023.02.24 |
---|---|
[C++/PGS] Lv.1 : ์ฒด์ก๋ณต (GREEDY) (0) | 2023.02.23 |
[C++/PGS] Lv.3 : ๋คํธ์ํฌ (DFS/BFS) (0) | 2023.02.23 |
[C++/PGS] Lv.2 : ํ๊ฒ ๋๋ฒ (DFS) (0) | 2023.02.23 |
[C++/PGS] Lv.2 : ๊ฒ์ ๋งต ์ต๋จ๊ฑฐ๋ฆฌ (BFS) (0) | 2023.02.23 |