🌞문제

가장 기본적인 dp문제인 최소경로 문제였다.

🌞접근법

맨 처음에 풀이는 재귀함수를 이용해서 먼저 dp의 틀을 만들어 주었다.
만들고보니 역시나 효율성에서 걸리는 것을 확인 할 수 있었다.
그러면 여기서 어떻게 재귀를 줄여야 하는가에 대해서 생각을 했다.

재귀함수를 반복문으로 바꿔주면 되겠다고 결론을 내렸다.
그 이유는 왼쪽과 오른쪽으로 이동이 가능한 이 제약사항은 이동만 가능하다면 최소 경로로 간다는 것을 의미한다.

따라서 그리드구조 상의 map에서 특정한 (x,y) 좌표의 최소 경로에 대한 횟수는 윗 칸의 최소경로+왼쪽 칸의 최소경로이다.

위의 내용을 토대로 결과를 도출 할 수 있었다.

🌞풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;


int place[101][101];

void dp(int x, int y)
{

    if(place[1][2] != -1) place[1][2] = 1;
    if(place[2][1] != -1) place[2][1] = 1;
    
    for(int i=1; i<=y; i++)
    {
        for(int j=1; j<=x ;j++)
        {
            if(place[j][i] != -1)
            {
                if(j-1 <= x && place[j-1][i] != -1) place[j][i] += place[j-1][i] %1000000007;
                if(i-1 <= y && place[j][i-1] != -1) place[j][i] += place[j][i-1] %1000000007;
                place[i][j] = place[i][j] % 1000000007;
            }
        }
    }
}

int solution(int m, int n, vector<vector<int>> puddles) {

    int answer = 0;
    for(int i=0;i<puddles.size();i++)
    {
        place[puddles[i][0]][puddles[i][1]]=-1;
    }
    
    dp(m,n);
    
    answer = place[m][n];
    
    return answer % 1000000007;
}

/*

1,1 에서 m,n으로 가는 방법은 일단 학교의 위쪽이나 왼쪽에는 도착을 해야한다.
위쪽이나 왼쪽에 도착을 하기 위해서는,
위쪽의 위쪽또는 왼쪽에 도착을 하거나, 왼쪽에 위쪽이나 왼쪽에 도착을 해야한다.
각 칸의 도착하는 횟수의 최소를 저장한다.
만약의 그 칸이 puddles에 있다면, 그칸은 -1로 한다.

*/

10억으로 나누는 것에서 계속 문제가 있어서 오래 걸린 문제였다.
int로 저장한 값들이 int를 초과하지 않게끔 해야 하는 것을 망각하고 풀다보니 효율성에서 다 실패가 나왔다.