[Programmers, C++] 등굣길

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

프로그래머스

 

 

 

 

#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> map(n + 1, vector<int>(m + 1, 1));

    for (auto p : puddles) {
        map[p[1]][p[0]] = 0;
    }
    

    dp[1][1] = 1;
    
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (map[i][j] == 0) {
                dp[i][j] = 0;
            } else {
                if (i > 1) dp[i][j] += dp[i - 1][j];
                if (j > 1) dp[i][j] += dp[i][j - 1];
                dp[i][j] %= 1000000007;
            }
        }
    }
    
    return dp[n][m];
}

 

 

 

집의 좌표는 (1,1) 이며 목적지의 좌표는 (m,n) 이다. 특이사항이라고 한다면 무조건 오른쪽 혹은 아래쪽으로만 움직일 수 있다는 것이다.

먼저 웅덩이가 있는 곳의 값은 0으로 설정을 해준다. 

 

 

 

 

이동이 오른쪽과 아래쪽으로만 가능하니 어떤 지점으로 갈 수 있는 방법의 종류는 (바로 윗 칸 + 바로 왼쪽 칸)으로 점화식을 세울 수 있다.

1번, 2번과 같은 경우에는 제약이 있으나 3번과 같은 일반적인 경우에는 위의 점화식을 적용할 수 있다. 

 

 

프로그래머스 문제의 난이도가 백준에서 어떤 수준인지는 잘 모르겠지만 개인적으로 실버 하위 문제라고 느껴졌다.