[프로그래머스] 등굣길

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

프로그래머스

 

프로그래머스 코딩 테스트 고득점 Kit에 포함된 Level 3 DP 문제입니다.

 

#include <string>
#include <vector>

using namespace std;

const int MOD = 1000000007;
int x, y, dp[101][101];
bool flag[101][101];

void init(vector<vector<int>>& puddles){
    for(vector<int> puddle : puddles){
        x = puddle[0];
        y = puddle[1];
        flag[y][x] = 1;
    }    
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    init(puddles);
    
    dp[1][1] = 1;
    
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(i == 1 && j == 1) continue;
            if(flag[i][j]) continue;
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
        }
    }
    
    answer = dp[n][m];
    return answer;
}

 

DP 문제이므로 항상 그랬던 것처럼 다음의 3단계로 풀이합니다.

 

1) table 정의

dp[i][j] : i행 j열까지 갈 수 있는 최단경로의 개수

 

2) 점화식 찾기

if(flag[i][j]) continue; // 물에 잠겼을 경우 그곳까지 갈 수 있는 최단경로의 수는 0이므로 continue;

dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;

 

3) 초기값 설정

dp[1][1] = 1;

 

물에 잠긴 곳을 flag 배열을 통해 체크해 주면 그 이후에는 쉬운 문제입니다. 지금까지 풀어온 BOJ 골드, 플래티넘 문제에 비하면 프로그래머스 Level 3까지는 체감상 난이도가 어렵지 않은 듯합니다.