[Programmers] C++ 동적계획법(DP) - 등굣길

 

[Programmers] C++ 동적계획법(DP) - 등굣길

 

문제 설명

 

문제 자체는 사실 어렵지 않다.

 

물웅덩이는 계산에 포함되지 않도록 미리 visited 처리 해놓고,

오른쪽, 아래쪽으로만 움직일 수 있기 때문에 DP(i,j) 에서 DP(i-1, j) + DP(i, j-1) 값을 할당해주면 된다.

 

격자 크기 m, n 도 각각 100 이하 값이고

물에 잠긴 지역(puddles)도 0개 이상 10개 이하이기 때문에 값 자체가 다 작아서 별 생각 안하고 풀 수 있다.

 

제한사항

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

 

 

풀이 ( 오답 )

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> board(101, vector<int>(101, 0));
    vector<vector<int>> visited(101, vector<int>(101, 0));
    board[1][1] = 1;
    for(auto puddle: puddles) {
        visited[puddle[0]][puddle[1]] = 1;
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(visited[i][j]) continue;
            if(i - 1 >= 1) {
                board[i][j] += board[i-1][j];
            }
            if(j - 1 >= 1) {
                board[i][j] += board[i][j-1];
            }
        }
    }
    answer = board[m][n] % 1000000007;
    return answer;
}

 

처음엔 그냥 문제에 지시한대로 마지막에 1,000,000,007로 나누면 답이 나올거라고 생각했다.

그런데 정확성 테스트에서는 테스트케이스를 다 맞췄지만,

효율성 테스트에서 모두 실패가 나왔다.

 

 

풀이 ( 정답 )

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> board(101, vector<int>(101, 0));
    vector<vector<int>> visited(101, vector<int>(101, 0));
    board[1][1] = 1;
    for(auto puddle: puddles) {
        visited[puddle[0]][puddle[1]] = 1;
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(visited[i][j]) continue;
            if(i - 1 >= 1) {
                board[i][j] += board[i-1][j] % 1000000007;
            }
            if(j - 1 >= 1) {
                board[i][j] += board[i][j-1] % 1000000007;
            }
        }
    }
    answer = board[m][n] % 1000000007;
    return answer;
}

 

 

for문을 도는 과정에서 숫자가 너무 커질 경우에 효율성이 걸리는 문제였다.

long long으로 처리를 해줘도 해결되지 않았고,

계산 중간마다 나머지처리를 해줬더니 효율성 테스트를 해결할 수 있었다.