Programmers : 등굣길

문제링크

풀이요약

DP

풀이상세

1. 임의의 좌표에 대하여 학교로 향하는 방향은, 가는 길이 물이 잠겨있지 않다면 아래로 내려가는 것과, 오른쪽으로 가는 것 총 2가지이다.

2. 따라서 점화식은 상단 이전좌표까지 도달하는데 나오는 모든 경우의 수 + 왼편 이전좌표까지 도달하는 나오는 모든 경우의 수이다.

3. 단, 이전좌표가 물이 잠긴 상태라면, 해당 이전좌표의 경우의 수는 반영하지 않는다.

4. 모듈러 연산을 하면서 나온 a[n][m] 의 결과값을 반환한다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int a[104][104];
const int INF = 1e9+7;
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;

    for(int i=0; i<puddles.size(); i++) {
        a[puddles[i][1]][puddles[i][0]]=-1;
    }
    
    a[1][1] = 1;
    for(int i=2; i<=n; i++) {
        a[i][1] = a[i][1] == -1 ? a[i][1] : a[i-1][1];
    }
    for(int j=2; j<=m; j++) {
        a[1][j] = a[1][j] == -1 ? a[1][j] : a[1][j-1];
    }

    
    for(int i=2; i<=n; i++) {
        for(int j=2; j<=m; j++) {
            if(a[i][j]==-1) continue;
            int r = a[i-1][j] == -1 ? 0 : a[i-1][j];
            int c = a[i][j-1] == -1 ? 0 : a[i][j-1] ;
            a[i][j]=(r+c)%INF;
        }
    }
    
    return a[n][m]%INF;
}