백준 1520 내리막 길

문제 URL : https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

문제접근법 : 

(0,0) 위치에서 좌우상하 방향으로 자신의 숫자보다 작은숫자면 이동합니다. 그렇게해서 이동했을때 (n-1,m-1)로 도착했을때의 경로를 구하는데

 

그림과 같이 움직일수있습니다. 그렇지만 이그림을 잘보시면 경로가 겹쳐있는 부분이 있습니다.

세그림중 어떤것이 먼저인지는 알수없으나 왼쪽그림부터 순서대로 도착했다고 가정한다면

두번째그림에선

(3,3)은 첫번째그림에서 그곳을 밟았을때 도착지까지 도착할수 있는 길이란걸 알수있습니다.

긍렇기에 (3,3)까지의 경로만 밟고 해당경로의수를 리턴해주면되고

3번째그림은 (1,3)을 밟을때 두번째그림에서 그땅을 밟을때 완주할수있다는것을 알수있습니다.

아래그림처럼

 

따라서 dp를 이용해서 계산하지 않아도될 길을 피하면서 메모이제이션 기법으로 dp를 활용하여 풀수있습니다.

 

소스코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; vector<vector<int>> board,dp; int dy[4] = { -1,0,1,0 }; int dx[4] = { 0,1,0,-1 }; int n, m; void input() {     cin >> n >> m;     board = vector<vector<int>>(n, vector<int>(m));     dp = vector<vector<int>>(n, vector<int>(m, -1));     for (int i = 0; i < n; i++) {         for (int j = 0; j < m; j++) {             cin >> board[i][j];         }     } } bool isrange(int y, int x) {     return 0 <= y && y < n && 0 <= x && x < m; } int dfs(int y, int x) {     int& cur = dp[y][x];     if (y == n - 1 && x == m - 1)         return cur=1;     if (cur > -1)         return cur;     int sum = 0;     for (int i = 0; i < 4; i++) {         int ny = y + dy[i];         int nx = x + dx[i];         if (isrange(ny, nx) && board[y][x] > board[ny][nx])             sum += dfs(ny, nx);     }     return cur = sum; }   void solve() {     cout << dfs(0, 0) << "\n"; } int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     //freopen("input.txt", "r", stdin);     input();     solve(); }     Colored by Color Scripter

cs

 

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.