[프로그래머스/Level 3] 등굣길 (C++)

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

코딩테스트 연습 - 등굣길

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

각각의 좌표는 해당 좌표를 갈 수 있는 경우의 수를 의미한다. 학교를 기준으로 왼쪽과 위에서 계속 합쳐지면서 경우의 수가 구해진다.  (위의 그림을 보면 이해가 갈 것이다.) 이를 통해 얻을 수 있는 점화식은 다음과 같다.

dp[n][m] = dp[n - 1][m] + dp[n][m - 1]

 

#include <string>
#include <vector>
using namespace std;

int map[101][101], dp[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    for(int i = 0; i < puddles.size(); i++) {
        map[puddles[i][1]][puddles[i][0]] = 1; // 웅덩이 표시
    }
    
    dp[0][1] = 1; // dp[1][1](시작점)을 1로 만들기 위한 초기값 설정
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(map[i][j] == 1) dp[i][j] = 0; // 웅덩이인 경우 갈 수 없으므로 경우의 수 0
            else dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
        }
    }
    
    return dp[n][m];
}