[프로그래머스 C++] 등굣길

[프로그래머스 C++] 등굣길

 

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

---

 

 

해결전략

 

동적계획법 Dynamic Programming

---

 

 

정답코드

 

#include <cmath>
#include <vector>
using namespace std;
 
int solution(int m, int n, vector<vector<int>> puddles) {
   
    vector<vector<int>> v(n + 1, vector<int>(m + 1, 0));
 
    for (int i = 0; i < puddles.size(); i++) {
        v[puddles[i][1]][puddles[i][0]] = -1;
    }
 
    v[1][1] = 1;
 
    for (int y = 1; y <= n; y++) {
        for (int x = 1; x <= m; x++) {
            if (y == 1 && x == 1) continue;
            if (v[y][x] == -1) continue;
            
            if (v[y - 1][x] == -1 && v[y][x - 1] == -1){
                v[y][x] = 0;
            }
            else if (v[y - 1][x] == -1 && v[y][x - 1] != -1) {
                v[y][x] = v[y][x - 1];
            }
            else if (v[y - 1][x] != -1 && v[y][x - 1] == -1) {
                v[y][x] = v[y - 1][x];
            }
            else{
                v[y][x] = (v[y - 1][x] + v[y][x - 1]) % 1000000007;
            }
        }
    }
 
    return v[n][m];
}

 

 

---