[코딩테스트 C++]등굣길

오늘의 문제

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

등굣길

나의 풀이

#include <string>
#include <vector>
using namespace std;

int solution(int n, int m, vector<vector<int>> puddles) {

    if(m == 1 || n == 1){
        if(puddles.size()!= 0)
            return 0;
        else
            return 1;
    }
    vector<vector<long long>> dp(m, vector<long long>(n, 0));
    
    for(int i=0;i<puddles.size();i++){ // 물에 잠긴곳 표시
        dp[puddles[i][1]-1][puddles[i][0]-1] = -1;
    }
    
    for(int i=0;i<n;i++){ // 초기화
        if(dp[0][i] == -1)
            break;
        dp[0][i] = 1;
    }
    for(int i=0;i<m;i++){
        if(dp[i][0] == -1)
            break;
        dp[i][0] = 1;
    }
    
    for(int i=1;i<m;i++){ // 경로 표시
        for(int j=1;j<n;j++){
            if(dp[i][j] == -1)
                continue;
            else{
                if(dp[i][j-1] != -1)
                    dp[i][j] += dp[i][j-1];
                if(dp[i-1][j] != -1)
                    dp[i][j] += dp[i-1][j];
                dp[i][j] = dp[i][j]%1000000007;
            }
        }
    }
    
    return dp[m-1][n-1];
}

모범 답안

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int loc[m][n];

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            loc[i][j] = 0;

    for (vector<int> p : puddles)
        loc[p[0]-1][p[1]-1] = -1;

    for (int i = 0; i < m; ++i)
    {
        if (loc[i][0] == -1)
            break;
        loc[i][0] = 1;
    }

    for (int i = 1; i < n; ++i)
    {
        if (loc[0][i] == -1)
            break;
        loc[0][i] = 1;
    }

    for (int i = 1; i < m; ++i)
        for (int j = 1; j < n; ++j)
        {
            if (loc[i][j])
                continue;

            if (loc[i-1][j] != -1)
                loc[i][j] += loc[i-1][j];
            if (loc[i][j-1] != -1)
                loc[i][j] += loc[i][j-1];

            loc[i][j] %= 1000000007;
        }

    return loc[m-1][n-1];
}

배울 점

• dp를 생각하게 되면서 가장 잘 생각해야할 부분은 무엇을 memorizing할것인가이다. 경로의 개수를 물어봤으니 경로의 개수가 들어갈것이다. 그렇게 생각하면서 슥 풀렸다.
• 하나 걸렸던 점은 초기화를 할 때 잠긴 곳이 초기화 부분에 있을것을 고려하지 않았다. 다행히 잡아내어 문제를 풀 수 있었다. 역시 입력에 대한 여러 경우의 고려가 필요하다.
• 모범답안과 로직이 같다 뿌듯