[프로그래머스 ]동적계획법(Dynamic Programming) > 등굣길

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

코딩테스트 연습 - 등굣길

[풀이방법]

이 문제는 n, m 이 y, x 이다.

위치가 바뀌어져있어서 헷갈릴 수 삽질을 할 수가 있다.

최단 거리가 조건인데 이동가능한 방향이 오른쪽/아래쪽 두가지 방향으로밖에 이동할 수 없기 때문에

항상 x, y 에 있을 때 최단거리로만 이동할 수 밖에 없다.

따라서, 그냥 n, m 으로 이동 가능한 모든 경우의 갯수를 구하면 된다.

dp 식은 고로

dp[y][x] = dp[y-1][x] + dp[y][x-1] 인데 

우물이 있을 경우도 고려해줘야한다.

우물이 있을 경우, 0 으로 리턴해줘서 계산 결과에 영향을 주지 않도록 하자.

 

효율성 패스를 위해 dp 에 값을 업데이트 할때마다 % 100000007의 나머지 값으로 저장해주도록 했다.

 

[전체코드]

#include <string>
#include <vector>

using namespace std;

int dp[102][102];

int DP(int y, int x) {
    if(y < 1 || x < 1 || dp[y][x] == -1) return 0;
    
    if(dp[y][x] > 0)
        return dp[y][x];
    
    dp[y][x] = (DP(y-1, x) + DP(y, x-1))  % 1000000007;
    
    return dp[y][x];    
}

int solution(int m, int n, vector<vector<int>> puddles) {
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            dp[i][j] = 0;
    
    for(auto puddle: puddles) {
        dp[puddle[1]][puddle[0]] = -1;
    }
    dp[1][1] = 1;
    
    return DP(n, m);
}