프로그래머스-등굣길

문제 링크

1. 문제 접근 과정🧐

1. 해당 좌표에 도달하는 길의 수를 누적하면 되겠다고 파악
2. 처음 (1, 1)은 1로 시작
3. 물 웅덩이인 좌표는 갈 수 없으므로 0으로 만듦
4. (i, j) = (i - 1, j) + (i, j - 1) % MOD 하는 방식
   
   

2. 시행착오🤯

• 인덱스를 1부터 반복문을 시작해야 하는데 2로 시작하여 제대로 된 답을 얻지 못했다.
  • 1부터 시작해야 모든 칸을 볼 수 있기에 제대로 된 답을 얻는다.
  • 2부터 시작하면 집의 오른쪽 아래 부분부터 보는 것이라서 잘못된 답이다.
• 오답 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

const int MOD = 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {
    set<pair<int, int>> s;
    for(int i = 0; i < puddles.size(); i++) s.insert({puddles[i][0], puddles[i][1]});
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    dp[1][1] = 1;
    for(int i = 2; i <= m; i++){
        for(int j = 2; j <= n; j++){
            if(s.find({i, j}) != s.end()) dp[i][j] = 0;
            else dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]) % MOD;
        }
    }
    return dp[m][n];
}

3. 개선한 코드😄

• 인덱스를 1부터 시작하여 해결
  
• 정답 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

const int MOD = 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {
    set<pair<int, int>> s;
    for(int i = 0; i < puddles.size(); i++) s.insert({puddles[i][0], puddles[i][1]});
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    dp[1][1] = 1;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(i == 1 && j == 1) continue;
            if(s.find({i, j}) != s.end()) dp[i][j] = 0;
            else dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]) % MOD;
        }
    }
    return dp[m][n];
}

4. 회고💭

• DP 문제는 일단 규칙을 어떻게 된 것인지 잘 파악해야 한다.
• 문제의 조건에 따라 인덱스가 어디서부터 시작하는지 판단해야 한다.