등굣길

연구하는개발자 2021. 1. 29. 23:54

728x90

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

코딩테스트 연습 - 등굣길

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m =

programmers.co.kr

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


int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    int map[105][105] = {0,};
     for(int j=1; j<=m; j++){
        map[1][j] = 1;
    }
    
    for(int i=1; i<=n; i++){
        map[i][1]=1;
    }
    
     for(int i=0; i<puddles.size(); i++){
        int y = puddles[i][0];
        int x = puddles[i][1];
        map[x][y] = -1; //개수
     }
    
    for(int p=1; p<=n; p++){
        for(int q=1; q<=m; q++){
            
            if(p==1 && q==1){continue;}
            if(map[p][q]!=-1){
               map[p][q]= (map[p-1][q]+ map[p][q-1])%1000000007;
            }
            else{map[p][q]=0;}
          }
        }
    
    answer = map[n][m];
    return answer;
}