[동적계획법, 난이도 중하] 프로그래머즈, 등굣길

프로그래머즈의 효율성 테스트에서 숫자가 매우 커지면 실패를 출력한다는 것을 깨달았다.

%1000000007을 하지 않았더라도 정확성은 만점이지만, 효율성은 0점이 나온다.

레벨3답지 않게 접근법은 매우 간단하다.

 

dp[x][y] = (1,1) 부터 (x,y) 까지의 최단 경로의 수  

맨 처음에는 dp[1][1]을 1로 두고 시작한다. 시작점=도착점이라면 경로의 경우의 수가 1이기 때문이다.

오른쪽과 아래쪽 영역을 탐색해가며 현재 영역의 dp값을 그대로 탐색중인 영역의 dp값에 더해주면 된다.

물론 탐색한 영역에 물이 있다면 더해주지 않으면 된다.

 

테스트 케이스 10개 정확성, 효율성 모두 만점

 

#include <vector>
using namespace std;

long long dp[101][101];
bool water[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    for(int i=0;i<puddles.size();i++) water[puddles[i][0]][puddles[i][1]]=true;
    dp[1][1]=1;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(j!=n && !water[i][j+1]) dp[i][j+1]+=(dp[i][j]%1000000007);
            if(i!=m && !water[i+1][j]) dp[i+1][j]+=(dp[i][j]%1000000007);
        }
    }
    int answer=dp[m][n]%1000000007;
    return answer;
}