[알고리즘 C++] 프로그래머스 - 등굣길

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

코딩테스트 연습 - 등굣길

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int dp[101][101]; // 격자 크기가 0 ~ 100

int solution(int m, int n, vector<vector<int>> puddles) {
    dp[1][1] = 1; // 집이 있는 곳을 (1,1)
    for (int i = 0; i < puddles.size(); i++) { 
        dp[puddles[i][1]][puddles[i][0]] = -1; // 물이 잠긴 곳은 -1
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int eve_down = 0;
            int eve_right = 0;
            if (dp[i][j] == -1)
                continue;
            if (dp[i - 1][j] != -1)
                eve_down = dp[i - 1][j];
            if (dp[i][j - 1] != -1)
                eve_right = dp[i][j-1];
            
            // 점화식 dp[i][j] += (dp[i - 1][j] + dp[i][j-1])
            dp[i][j] += (eve_down + eve_right) % 1000000007;
        }
    }
    return dp[n][m];
}

 

실행 결과