프로그래머스_등굣길(C++, JAVA)

 

 

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

프로그래머스

[문제 풀이]

DP를 이용하여 문제를 풀었습니다.

 

먼저 이차원 배열을 선언하여 우물을 체크 해주었고 이차원 배열 DP를 이용하여 풀었습니다. (1,1)의 지점에서 (m,n)까지 반복문을 돌며 처음 지점에 올 수 있는 방법은 한 가지인 것을 이용하여 dp[1][0] 을 1로 초기화해주며 다음 길로 올 수 있는 경우는 위에서 오는 것과 옆에서 오는 것을 고려하여 점화식을 짰습니다.

 

이코드의 핵심은

if (map[i][j] == -1)
    dp[i][j] = 0;
else
    dp[i][j] = (dp[i][j - 1] + dp[i-1][j]) % 1000000007;

입니다

[C++]

#include <string>
#include <vector>

using namespace std;

int map[101][101] = { 0, };
int dp[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;

    for (int i = 0; i < puddles.size(); i++)
        map[puddles[i][1]][puddles[i][0]] = -1;

    dp[1][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (map[i][j] == -1)
                dp[i][j] = 0;
            else
                dp[i][j] = (dp[i][j - 1] + dp[i-1][j]) % 1000000007;

        }
    }

    answer = dp[n][m];

    return answer;
}

 

[JAVA]

class Solution {

    public int solution(int m, int n, int[][] puddles) {
		
		int[][] dp = new int[n+1][m+1];
		int[][] map = new int[n+1][m+1];
		
		for(int[] item : puddles) {
			map[item[1]][item[0]] = -1;
		}
		
		dp[1][0] = 1;
		
		for (int i = 1; i <= n; i++) {
	        for (int j = 1; j <= m; j++) {

	            if (map[i][j] == -1)
	                dp[i][j] = 0;
	            else
	                dp[i][j] = (dp[i][j - 1] + dp[i-1][j]) % 1000000007;
	        }
	    }
		
        return dp[n][m];
    }
}