10) 프로그래머스 Lv.3 - 등굣길

코딩테스트 연습 - 등굣길 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

풀다가 김 빠진 문제.

#include <bits/stdc++.h>

using namespace std;

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

음.... 꽤나 고민 할 뻔한 문제....

puddle의 행과 열을 반대로 출제해서 시간만 버린 문제

이럴거면... 왜 예시를 [2, 2]로 주냐고.....

 

방법은 간단했다.

탐색 위치 왼쪽과 위쪽의 합을 계속 적어주면 되는 문제.처음에는 BFS 처럼 큐를 사용하려 했는데 효용성에서 전부 땡!....ㅠㅠㅠ때로는 간단한것이 좋을 때도 있구나..