[프로그래머스] 등굣길

문제요약

배열의 크기(m,n)와 물웅덩이의 위치가 입력으로 주어집니다.
항상(1,1)이 집이고 (m-1,n-1)이 학교일 때 오른쪽과 아래로만 움직여 학교로 갈 수 있는 등교길의 수를 구하시오.(mod 1,000,000,007)

삽질

m은 가로, n은 세로이다. 웅덩이의 위치또한 [가로좌표, 세로좌표]로 주어진다.
이걸 반대로 생각해서... 예제도 하필이면 [2,2]여서 캐치를 못했다..

새로 배운 거

memset

long long tab[100][100]={0,};과 같은 초기화는 0일 때만 가능하다.

#include<memory.h>
...
bool map[100][100];
memset(map,true,sizeof(map));

코드

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
using namespace std;
//오른쪽과 아래로만 이동 가능
bool map[100][100];
long long tab[100][100]={0,};
long long MOD= 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    memset(map,true,sizeof(map));
    for(int ctr = 0;ctr<puddles.size();ctr++){
        int i = puddles[ctr][1]-1,j = puddles[ctr][0]-1;
        map[i][j] = false;
    }
    if(map[1][0]) tab[1][0] = 1;
    if(map[0][1]) tab[0][1] =1;
    //세로를 1로 채운다.
    for(int i = 2;i<n;i++){
        if(map[i][0])
            tab[i][0] = tab[i-1][0];
    }
    //가로를 1로 채운다
    for(int j = 2;j<m;j++){
        if(map[0][j])
            tab[0][j] = tab[0][j-1];
    }
    //테이블의 나머지 네모를 채운다.
    for(int i = 1;i<n;i++){
        for(int j = 1;j<m;j++){
            if(map[i][j])
                tab[i][j] = (tab[i-1][j]+tab[i][j-1])%MOD;
        }
    }
    
    answer = tab[n-1][m-1];
    return answer;
}

경량화된 버전2

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
using namespace std;
//오른쪽과 아래로만 이동 가능
bool map[100][100];
long long tab[100][100]={0,};
long long MOD= 1000000007;
int m, n;

bool inbox(int i, int j){
    return i>=0&&i<n&&j>=0&&j<m;
}
int solution(int mm, int nn, vector<vector<int>> puddles) {
    int answer = 0;
    m = mm; n=nn;
    memset(map,true,sizeof(map));
    for(int ctr = 0;ctr<puddles.size();ctr++){
        int i = puddles[ctr][1]-1,j = puddles[ctr][0]-1;
        map[i][j] = false;
    }
    tab[0][0] = 1;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(i == 0&&j ==0) continue;
            if(map[i][j]){
                tab[i][j] = ((inbox(i-1,j)?tab[i-1][j]:0)+(inbox(i,j-1)?tab[i][j-1]:0))%MOD;
            }
        }
    }
    
    answer = tab[n-1][m-1];
    return answer;
}