[프로그래머스] 등굣길

문제

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

접근 방법

DP를 이용한다. dp[i][j] 는 i, j로 갈 수 있는 길의 개수
dp[i][j] == 물웅덩이 -> -1로 초기화 하고
dp[i][j] += 왼쪽에서 올 경우(물웅덩이가 아닐 때) + 위쪽에서 올 경우(물웅덩이가 아닐 때) 이다.
값이 커지는 것을 방지해 1000000007로 나누어준다.

풀이

#include <string>
#include <vector>

using namespace std;

int dp[101][101]; 

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    dp[1][1] = 1;
    for(vector<int> puddle : puddles)
    {
        dp[puddle[1]][puddle[0]] = -1;
    }
    
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            // 물웅덩이는 패스
            if (dp[i][j] == -1)
                continue;
            
            int a = 0;
            int b = 0;
            if (dp[i-1][j] != -1) // 위쪽이 물웅덩이가 아닐 경우
                a = dp[i-1][j];
            if (dp[i][j-1] != -1) // 왼쪽이 물웅덩이가 아닐 경우
                b = dp[i][j-1];
            dp[i][j] += (a+b) % 1000000007;
        }
    }
    return dp[n][m];
}

정리

DP 연습을 많이 하자자!