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

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 출발지에서 도착지까지 도달하는 최단경로의 개수를 return하는 문제다.

 

여기서 방향은 항상 오른쪽 아래로 움직이기 때문에, 일정 횟수를 움직여서 도달할 수 있는 위치는 정해져 있다.

 

그러므로 n칸 움직여서 도달할 수 있는 위치는 위와 왼쪽방향에 있는 n-1칸 움직여서 도달할 수 있는 곳의 경우의 수의 합과 같다.

 

아래 그림을 참고하면 이해가 쉬울 것이다. 

위 그림과 같이 1, 1이 출발지 3, 4가 도착지라고 하면 각 칸까지 이동하는데 걸리는 경우의 수를 나타낼 수 있다.

 

예를 들어 (2,2)에 도달하는 경우의 수는 (1,2)에서 아래로 이동하는 경우와 (2,1)에서 오른쪽으로 이동하는 경우가 있다.

그러므로 (2,2) = (1,2) + (2,1)로 나타낼 수 있는 것이다.

 

이와 같은 규칙을 이용해 현재 칸에 올 수 있는 경우의 수 = 위와 왼쪽에 있는 칸에 올 수 있는 경우의 수로 반복계산해 문제를 해결했다.

 

+ puddles에 있는 칸은 이동할 수 없으므로 -1을 대입해 계산에서 제외시켜주었다.

 

 

[아이디어 정리]

1. 현재 칸에 도달할 수 있는 경우의 수는 왼쪽칸에서 오는 경우의 수 + 위 칸에서 내려오는 경우의 수를 더한 값과 같다.
2. 2차원 vector를 만들고 1번규칙을 적용한다.
3. 만약 현재 칸이 puddles에 있다면, 계산하지 않는다.
4. 모든 계산이 끝난 후 도착지에 있는 값을 return한다.

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;
const int Mod=1000000007;
int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<int>> DP(n+1,vector<int>(m+1,0));
    DP[1][1]=1;
    for (int i=0; i<puddles.size(); i++)
    {
        DP[puddles[i][1]][puddles[i][0]]=-1;
    }
    for (int y=1; y<=n; y++)
    {
        for (int x=1; x<=m; x++)
        {
            if (DP[y][x]!=-1)
            {
                if (DP[y-1][x]!=-1)
                    DP[y][x]+=DP[y-1][x]; 
                if (DP[y][x-1]!=-1)
                    DP[y][x]+=DP[y][x-1];  
                DP[y][x]%=Mod;
            }
        }
    } 
    return DP[n][m];
}

 

---

 

처음에 크기를 n, m으로 설정해 index의 범위를 체크했는데, 생각해보니  n+1, m+1로 index를 늘려 쉽게 해결할 수 있었다... EZ

 

 

프로그래머스