[프로그래머스 등굣길] c++ (풀이,코드,dp)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

문제

 

풀이 및 코드

 

이 문제의 핵심은 아마 오른쪽과 아래쪽으로만 움직여라고 생각합니다.

 

우리는 그것을 바탕으로 이제 dp를 사용할 수 있습니다.

 

집	1	1	1	1	1
1
1
1					학교

우리가 오른쪽으로 이동할 수 있는 것은 모두 맨끝으로가도 당연히 1가지 입니다.(아래도 똑같고요)

집	1	1	1	1	1
1	1+1 =2	2+1= 3	3+1=4	4+1=5	5+1=6
					학교

이렇게 두번째 줄에 대해서 처리를 할때 위와 왼쪽의 합을 구하게 되면 됩니다.

 

이제 웅덩이가 있을때에 대해서 예시를 보겠습니다.

집	1	1	1	1	1
1	웅덩이	0+1 =1	1+1 =2	2+1 =3	3+1 =4
1	1	1+1 =2	2+2=4	..	..
1					학교

이런식으로 웅덩이를 무시하고 갯수를 더하게 되면 됩니다.

            //위랑 왼쪽에 대해 범위 안 그리고 웅덩이x일때 추가

            if(i-1 >= 0 &&dp[i-1][j] != -1 && dp[i][j] != -1){

                dp[i][j] += dp[i-1][j];

            }

            if(j - 1 >= 0 && dp[i][j-1] != -1 && dp[i][j] != -1){

                dp[i][j] += dp[i][j-1];

            }

그것을 이러한 형태로 처리를 완료하였습니다. 

1. 범위 내

2. 내 자리가 웅덩이가 아니고 또한 받으려는 자리도 웅덩이가 아니어야함.

전체 코드

 

/*

잠기지 않은 지역을 통해 학교를 가려함

시작은 왼쪽위 도착지점은 오른쪽 아래이니

지점에 대해서 왼쪽과 위에 대한 갯수를 더해서 dp를 하면 되지 않을까 싶다.

왜냐하면 오른쪽아니면 아래만 이동이 가능하기 때문

*/

#include <string>

#include <vector>

#include <iostream>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {

    int answer = 0;

    int dp[100][100]={0,};

    dp[0][0] = 1;

    for(int i = 0; i < puddles.size();i++){

        dp[puddles[i][1] - 1][puddles[i][0] - 1] = -1; // -1은 웅덩이

    }

   

    for(int i = 0; i < n;i++){

        for(int j = 0; j < m;j++){

            //위랑 왼쪽에 대해 범위 안 그리고 웅덩이x일때 추가

            if(i-1 >= 0 &&dp[i-1][j] != -1 && dp[i][j] != -1){

                dp[i][j] += dp[i-1][j];

            }

            if(j - 1 >= 0 && dp[i][j-1] != -1 && dp[i][j] != -1){

                dp[i][j] += dp[i][j-1];

            }

            dp[i][j] %= 1000000007;

        }

    }

    return dp[n-1][m-1];

}