[c++/프로그래머스] 등굣길

문제 링크

등굣길

풀이

dq로 푸는 문제. 효율성에서 삑나는게 왜인가 했는데 더할 때마다 나머지 해주면 안됨...ㅋ
더해놓고 1000000007이 넘으면 나머지 계산해줘야 한다.

1. 일단 출발 지점인 v[0][0]은 1이고, 웅덩이가 있는 곳은 -1로 초기화 해준다.
2. 어차피 오른쪽이나 아래쪽으로만 움직이니까 그냥 이중반복문 써서 처리해주면 된다.
   2-1. v[i][j]가 웅덩이면 continue
   2-2. v[i][j]의 위쪽까지 오는 경우의 수와 왼쪽까지 오는 경우의 수를 더해준다. (범위 내일 경우만)
   즉, 점화식은 v[i][j] = v[i-1][j] + v[i][j-1]
   2-3. 구했을 때 수가 1000000007이 넘는다면 나머지 값을 넣어준다.
3. answer 값은 v[n-1][m-1]이 된다.

코드

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

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;

    vector<vector<int>> v(n, vector<int>(m));
    v[0][0] = 1;
    
    for (int i = 0;i < puddles.size();i++)
    {
        v[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
    }
    
    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < m;j++)
        {
            if (v[i][j] == -1) continue;
            if (i - 1 >= 0 && v[i - 1][j] != -1) // 위에 칸이 있을 때
                v[i][j] += v[i - 1][j];
            if (j - 1 >= 0 && v[i][j-1] != -1) // 왼쪽에 칸이 있을 때
                v[i][j] += v[i][j - 1];
            if(v[i][j]>=1000000007) v[i][j]%=1000000007;
        }
    }

    answer = v[n - 1][m - 1];

    return answer;
}