[C++/PGS] Lv.3 : 등굣길 (DP)

동적 계획법 (Dynamic Programming) : 등굣길

문제 출처 - 프로그래머스 코딩테스트 고득점 Kit

 

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

---

 

어쩐지 문제가 x,y 좌표도 거꾸로 되어있고 나머지를 구하라는 그런 더럽고 복잡한 문제였는데,

악명 높기로 유명한 문제였다.

 

질문 게시판에 욕이 조금 많은.^^

 

근데 진짜 그럴만함

난 바로 알아채긴 했는데 좌표 x,y 반대인거 몰랐던 사람들은 한참 삽질하다가 풀었을테고

막상 풀어서 정답은 맞아도, 효율성 테스트에서 0점이 나와서 헤맨 사람들도 많다

당신만 그랬던게 아니니 안심하세요! 라는 의미입니다

 

나도 효율성 때문에 통과를 못했었는데, 일단 무조건 dp로 풀어야 하고 (정확히는 모름)

dp값을 구할 때 마다 % 1000000007를 해주면 통과하더라..ㅎㅎ

 

조건 따질게 많아서 까다로웠다.

 

1. (1,1)은 항상 1이다.

2.(1,y) 은 위쪽 값 그대로, (x,1)은 왼쪽 값을 그대로 가져와야 함. 이거 제대로 처리 안하면 (1,2)(2,1)에 물웅덩이가 있을 때 원래 답은 0이 나와야 하지만,  다른 결과값이 나오는 불상사가 생긴다

3. 우리 PS 상식으로는 (n,m)이 행과 열이기 때문에... 이 문제에서는 (m,n)으로 풀어야함 

4. 기본 테스트케이스가 구려서 질문하기 게시판에서 추가로 찾아보는거 추천

 

여러가지로 뇌절 문제였다;;

 

 

 

 

나의 풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int dp[102][102]={{0,}};
    dp[0][0] = 1;
    dp[1][1] = 1; dp[1][2] = 1; dp[2][1] = 1;
    
    for(int i=0; i<puddles.size(); ++i){
        dp[puddles[i][0]][puddles[i][1]] = -1;
    }
    
    for(int j=1; j<=m; ++j){
        for(int i=1; i<=n; ++i){
            if(i==1&&j==1) continue;
            if(dp[j][i]==-1){ 
                dp[j][i] = 0; 
                continue; 
            }
            if(i==1){
                dp[j][i] = dp[j-1][i];
                continue;
            }
            if(j==1){
                dp[j][i] = dp[j][i-1];
                continue;
            }
            dp[j][i] = (dp[j-1][i] + dp[j][i-1])% 1000000007;
        }
        cout<<"\n";
    }
    answer = dp[m][n];
    return answer;
}