프로그래머스 - 등굣길 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

 

문제 풀이

[1][1]에서 [2][2]로 이동할 수 있는 경우의 수는
(오른쪽으로 이동 -> 아래로 이동), (아래로 이동 -> 오른쪽으로 이동)의 2가지이다.

 

따라서 점화식을 세워보면 이동할 수 있는 경우의 수는
i가 행, j가 열일 때 DP[i][j] = DP[i-1][j] + DP[i][j-1]로 누적되어 나간다.

 

DP로 더해나갈 때, 물에 잠긴 지역은 -1로 표시해두고 더하지 않는다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int DP[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    DP[1][1] = 1;
    
    for(int i=0; i<puddles.size(); i++){
        DP[puddles[i][1]][puddles[i][0]] = -1;
    }
    
    for(int i=1;i<=n; i++){
        for(int j=1; j<=m; j++){
            int a = 0, b = 0;
            
            if(DP[i][j] == -1) continue;
            if(DP[i-1][j] != -1) a = DP[i-1][j];
            if(DP[i][j-1] != -1) b = DP[i][j-1];
            
            DP[i][j] += (a + b) % 1000000007;
        }
    }
    
    return DP[n][m];
}

 

 

주의해야할 점

처음에 DP[101][101] 배열을 solution 함수 안에서 선언하였더니
효율성 테스트 10에서 실패하였다.

 

코드를 이것저것 수정해보다가 DP 배열이 전역변수로 선언될 때 통과하는 것을 보고 생각을 해봤다.

 

아마 프로그래머스 시스템이 main문 안에서 여러 테스트케이스에 대해 solution 함수를 호출하는데
이 때마다 DP 배열이 계속 다시 선언되며 효율성 테스트에 실패하는 것 같다.

 

항상 큰 배열을 선언할 때는 전역 변수로 선언하는 습관을 가져야겠다.