[Algorithm] Programmers :: 등굣길

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

프로그래머스

#define MAX_NUM 1000000007
int dp[102][102];
 
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
 
    dp[1][1] = 1;
 
    for (int i = 0; i < puddles.size(); ++i)
    {
        dp[puddles[i][1]][puddles[i][0]] = -1;
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (dp[i][j] == -1)
            {
                dp[i][j] = 0;
                continue;
            }
 
            dp[i][j] = (dp[i][j] + dp[i - 1][j] + dp[i][j - 1]) % MAX_NUM;
        }
    }
 
    return dp[n][m] % MAX_NUM;
}

예~전에 시도했다가 못풀고 우연히 다시 접한 문제이다.

어제부터 그냥 프로그래머스문제좀 풀고 있었는데, 우연히 하나 집은 문제가 예전에 못푼 문제였다.

근래에 DP문제를 좀 풀었었는데, 다시 이 문제를 보자마자 DP문제인 걸 알았다.

근래에 DP문제를 안풀어봤었더라면 알 수 있었을까..? 

진짜 문제를 굉장히 많이 풀어봐야한다. 

 

그리고 애초에 이런 문제유형이 꽤 자주보이는것 같으니 숙지해놔야 할 것 같다.

어젠가 그저께에 이 문제조건 + 방향까지 있는 문제를 풀이했었기 때문에 프로그래머스 3레벨짜리 문제중 가장 빨리 푼 것 같다.