[프로그래머스] 등굣길 / DP, Dynamic Programming

문제 링크

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

프로그래머스

 

풀이 접근

물에 잠기지 않은 어떠한 지역에 대해 그 곳에 오는 방법은 바로 위쪽 지역에서 오는 방법(1)과 바로 왼쪽 지역에서 오는 방법(2)이 있다.

따라서 현재 지역으로 오는 방법의 수는 (1)과 (2)의 합으로 나타낼 수 있다. 시작 지역(집)에 오는 방법을 1로 초기화 하고 다른 지역들에 도착하는 방법의 수를 갱신해나가면 된다.

 

코드

#include <string>
#include <vector>
#define DIV (1000000007)
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int map[101][101];
    for (int x = 1; x <= m; ++x) {
        for (int y = 1; y <= n; ++y) {
            map[x][y] = 0;
        }
    }

    for (const auto& p : puddles) {
        map[p[0]][p[1]] = -1;
    }

    map[1][1] = 1; //집
    
    for (int x = 1; x <= m; ++x) {
        for (int y = 1; y <= n; ++y) {
            if (map[x][y] == -1) { continue; } //물에 잠긴 지역은 스킵
            
            //어떤 물에 잠기지 않은 지역의 왼쪽으로 부터 진입하는 경우
            int plx = x - 1; //previoius left x
            int ply = y; //previous left y
            if (plx >= 1 && ply >= 1 && plx <= m && ply <= n && map[plx][ply] != -1) {
                map[x][y] += map[plx][ply];
                map[x][y] %= DIV;
            }
				
            //어떤 물에 잠기지 않은 지역의 위쪽으로 부터 진입하는 경우
            int pux = x; //previous up x
            int puy = y - 1; //previous up y
            if (pux >= 1 && puy >= 1 && pux <= m && puy <= n && map[pux][puy] != -1) {
                map[x][y] += map[pux][puy];
                map[x][y] %= DIV;
            }
        }
    }

    answer = map[m][n];
    return answer;
}