백준 1890번 : 점프

  쉬운 문제인데 한 번 틀려서 괜히 자존심 상한다... 출력 값의 범위가 int를 벗어나서 생기는 문제여서 int로 선언한 dp 배열을 long long으로만 바꿔서 제출했더니 맞았다.ㅠㅠ

---

  풀이

  흔한 dp 문제다. 오른쪽 또는 아래쪽으로만 갈 수 있으므로 dp 계산을 위해 이중 for문 한 번만 사용하면 된다. 심지어 내가 쓴 코드에서 입력을 읽음과 동시에 바로 dp를 계산하면 아주 짧게 끝날 수도 있다.

 

dp [i][j] : i열 j행까지 도착할 수 있는 경우의 수

 

  시작은 항상 1열 1행이고 오른쪽, 아래쪽으로만 갈 수 있으므로 다시 되돌아가는 경우는 절대로 발생할 수 없다. 따라서 자신의 위치에 도달할 수 있고

 

dp[i][j] != 0

 

자신의 값이 종착점이 아니면

 

value[i][j] != 0

 

자신의 값만큼 오른쪽이나 아래쪽으로 움직일 수 있는 것이다.

 

dp [i+value [i][j]][j] += dp [i][j]

dp [i][j+value [i][j]] += dp [i][j]

 

#include <iostream>

using namespace std;

int n;
int value[102][102];
long long dp[102][102];

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> value[i][j];
        }
    }
    
    dp[1][1] = 1;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(dp[i][j] != 0 && value[i][j] != 0)
            {
                int v = value[i][j];
                dp[i+v][j] += dp[i][j];
                dp[i][j+v] += dp[i][j];
            }
        }
    }
    
    cout << dp[n][n];
    
    return 0;
}