[프로그래머스] 등굣길

문제

등굣길 (https://programmers.co.kr/learn/courses/30/lessons/42898)

풀이

1. 초기 접근

• 문제 조건 해석
  • m x n 격자 map이 등장한다. -> 이차원 배열 사용해야한다.
  • m, n은 1 이상 100 이하인 자연수-> O(n^2) 으로 풀린다. 다만 효율성 테스트가 있으므로, 그 중에서도 가장 퍼포먼스가 좋은 알고리즘을 선택해야한다.
  • 물에 잠긴 지역은 0개 이상 10개 이하입니다. -> 물 웅덩이 인지 아닌지 탐색하는 시간은 O(상수)
• 효율성 테스트
  • 이러한 문제를 푸는 것은 재귀 나 DP가 있다. 효율적인 것을 고려한다면, 함수 호출이 적고 스택에 메모리 쌓아가는 부담이 없는 DP가 훨씬 좋다.
  • 또한 1000000007로 나눠줘야함을 잊지 말자.
• 코드

#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int map[101][101] = {0,};
    int d[101][101];

    // set puddles into map.
    for (auto v : puddles)
        map[v[1]][v[0]] = -1;

    d[1][0] = 1;
    for (int i=1 ; i<=n ; i++) {
        for (int j=1; j<=m ; j++) {
            if (map[i][j] == -1)
                d[i][j] = 0;
            else 
                d[i][j] = (d[i-1][j] + d[i][j-1]) % 1000000007;
        }
    }
    return d[n][m];
}