[Level3.] 등굣길 C++

<< 문제 >> 

 

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

프로그래머스

 

 

<< 풀이 >>

 

dp로 해결하는 문제입니다. 

 

테이블에서 물 웅덩이가 되는 부분은 미리 -1로 설정하고, 테이블을 채워주면 되는 문제입니다. 

 

<< 코드 >>

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int table[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    for(auto& a : puddles){ // 물 웅덩이 표시
        table[a[0]][a[1]] = -1;
    }
    
    table[1][1] = 1; // 가장 처음 값 1로 설정
    
    for(int i = 1; i<=m; i++){
        for (int k=1; k<=n; k++){
            if(table[i][k] == -1){ // 물 웅덩이인 경우 
                continue;
            }
            
            int valRight = table[i][k-1] ;
            int valDown = table[i-1][k];
            if(valRight == -1){ // 왼쪽 칸이 물 웅덩이였던 경우 
                valRight = 0;
            }
            if(valDown == -1){ // 윗 칸이 물 웅덩이였던 경우 
                valDown = 0;
            }
            
            table[i][k] += (valRight + valDown) %  1000000007;
        }
    }
    
    answer = table[m][n];
    return answer;
}