[프로그래머스] 등굣길

 

 

문제 보러가기 : https://programmers.co.kr/learn/courses/30/lessons/42898

 

 

 

코딩테스트 연습 - 등굣길

 

 

이번 문제는 동적 프로그래밍 문제였습니다.

 

 

 

《문제 풀이》

 

1. 길의 정보를 나타내는 배열 road[101][101] 선언

2. 물이 잠긴 지역은 -1로 두어 경로의 개수를 세지 못하도록 방지

3. 누적 합을 위해 집의 위쪽 좌표 또는 왼쪽 좌표를 1로 두기 (본인은 왼쪽 좌표를 1로 두었음)

4. 해당 좌표가 -1 인 경우에는 0으로 두어 경로들의 합을 구함

 

 

 

《C++ 코드》

 

#include <string>
#include <vector>

using namespace std;

int road[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    for (int i=0; i<puddles.size(); i++) 
        road[puddles[i][1]][puddles[i][0]] = -1;
    
    road[1][0] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (road[i][j] == -1)
                road[i][j] = 0;
            else 
                road[i][j] = (road[i-1][j] + road[i][j-1]) % 1000000007;
        }
    }
    
    answer = road[n][m];
    return answer;
}

 

 

개발 환경: 프로그래머스

 

 

프로그래머스 - 정답 화면