[C++]프로그래머스 보행자 천국(동적 계획법 DP)

코딩테스트 연습 - 보행자 천국 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

#include <vector>

using namespace std;

int MOD = 20170805;

int solution(int m, int n, vector<vector<int>> city_map) {
    int answer = 0;
    int right[501][501] = {0,};
    int down[501][501] = {0,};
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == 1 && j == 1)
            {
                right[i][j] = 1;
                down[i][j] = 1;
            }
            else
            {
                if(city_map[i - 1][j - 1] == 0)
                {
                    right[i][j] = (right[i][j - 1] + down[i - 1][j]) % MOD;
                    down[i][j] = (right[i][j - 1] + down[i - 1][j]) % MOD;
                }
                else if(city_map[i - 1][j - 1] == 1)
                {
                    right[i][j] = 0;
                    down[i][j] = 0;
                }
                else
                {
                    right[i][j] = right[i][j - 1] % MOD;
                    down[i][j] = down[i - 1][j] % MOD;
                }
            }
        }
    }
    return down[m][n] % MOD;
}

이런 제대로된 DP 문제는 거의 처음이지 않을까... 역시 사람이 도전은 해봐야 되는 것 같다.

 

처음이라 이해하는 데도 무척이나 오래 걸렸지만...

 

2는 위에서 왔을때와 왼쪽에서 왔을 떄 그 경우의 수 값을 갱신해주지 않는다고 생각하면 편함.

 

0은 무조건 왼쪽에서 오는 right 값 + 위에서 오는 down값의 합이며, 그것이 곧 정답이며, 그것이 곧 그 위치에서의 right값이자 down 값임.

 

따라서 답은 right가 돼도, down이 돼도 상관없음.

 

+ dp배열을 구하는 과정에서는 MOD로 나눠도 항상 같은 답이 나옴

 

+ dp같은 문제는 이전 인덱스 참조 ( - 1)해야 하므로 주어진 2차원 벡터와는 달리 0,0 대신 1,1에서 시작해주어야 -1 했을 때 정상적으로 0을 도출하기 때문에 완전 별개의 테이블을 만들었다고 생각하면 편하다.

 

이 모든것은 결국 0이라는 곳에 도달했을 때의 경로값을 구하기 위한 행동들이다.