[프로그래머스 - 42898] 등굣길

- 문제설명

 

 

- 풀이코드

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
//https://programmers.co.kr/learn/courses/30/lessons/42898
 
int solution(int m, int n, vector<vector<int>> puddles) {
   
    int answer = 0;
    
    vector<vector<int>> DP(n+1,vector<int>(m+1,0));
 
    for(auto puddle : puddles){
        DP[puddle[1]][puddle[0]] = -1;
    }
    
    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(DP[i][j]== -1){
                DP[i][j] = 0;
                continue;
            }
            if(i==1) DP[i][j] = DP[i][j-1];
            else if(j==1) DP[i][j] = DP[i-1][j];
            else{
                DP[i][j] = (DP[i-1][j] + DP[i][j-1]) % 1000000007; 
            }
        }
    }
    
    answer = DP[n][m];
    
    return answer;
}

 

- 시간복잡도

 

O(nm)

 

- 남의 풀이와 비교

처음에 웅덩이를 일괄적으로 처리하지 않고 풀어서 시간초과가 났던 문제이다. 매번 해당 좌표가 웅덩이 인지 확인하게 되면 시간 복잡도가 O(nm)에서 최악의 경우 O((nm)^2)이 되버리기 때문이다. DP로 푸니까 시간복잡도에 대한 고민을 딱히 하지 않았는데 물 웅덩이를 처리하는 것도 생각을 해줬어야 하는 문제이다. 다른 사람들의 코드를 보면 조건과 DP 배열을 채우는 방식이 내 코드보다 좀더 깔끔했다. 조건 작성할 때 어떻게 하면 최적화 할 수 있는지 고민을 하는 습관이 필요하다고 생각이 들었다. 

 

- Reference

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