[C++] 프로그래머스 등굣길 DP

#include <string>
#include <cstring>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<int>> lists(n + 1, vector<int>(m + 1, 1));
    
    for(int i = 0; i <= m; i++)
        lists[0][i] = 0;
    for(int i = 0; i <= n; i++)
        lists[i][0] = 0;
    
    for(int i = 0; i < puddles.size(); i++)
        lists[puddles[i][1]][puddles[i][0]] = 0;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(lists[i][j] == 0) continue;
            if(i == 1 && j == 1) continue;
            
            lists[i][j] = (lists[i][j - 1] + lists[i - 1][j]) % 1000000007;	//여기서 계산을 해야됨
        }
    }
    
    return lists[n][m];
}

 

풀이

1. x - 1, y와 x , y - 1을 더하면 최종 개수가 나온다.
2. 1, 1은 시작지점이므로 패스한다.
3. 계산한 값을 1,000,000,007로 나눈 나머지를 값에 넣어야 효율성 테스트를 통과한다.