[C/C++] BOJ 1890 :: 점프

BOJ 1890 :: 점프

문제 링크 : https://www.acmicpc.net/problem/1890

자료형의 출력범위를 혼동해서.. unsigned int 로 했다가 틀렸다 ㅠㅠ 한 번에 맞출 수 있었는데...

그래도 문제를 보고 접근방식이 바로 생각났고 생각대로 코딩하여 답을 맞출 수 있어서 매우 뿌듯했다!

나의 풀이

DFS + DP 방식으로 문제 풀기

반환 조건

1. 종착역에 도착하면 1 반환

2. 이미 dp 배열에 값이 있으면 그 값 반환

3. 현재 board의 값이 0 이면 0 반환

반환된 값을 더하여 dp 배열 갱신 

==============================================================

나의 풀이 방법말고 처음부터 끝까지 순차적으로 dp 배열을 채워나가는 방법도 있다.

나의 코드 

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1890/BOJ_1890.cpp

// 백준알고리즘 1890번 :: 점프
#include<iostream>
using namespace std;
 
int N;
long long dp[101][101];
int visited[101][101];
int board[101][101];
 
// 하, 우
int dx[2] = { 1, 0 };
int dy[2] = { 0, 1 };
 
long long dfs(int x, int y)
{
    visited[x][y] = 1;
 
    if (x == N - 1 && y == N - 1) return 1;
    long long &ret = dp[x][y];
    if (ret) return ret;
    if (board[x][y] == 0) return ret;
 
    for (int i = 0; i < 2; i++)
    {
        int mx = x;
        int my = y;
 
        for (int j = 0; j < board[x][y]; j++)
        {
            mx += dx[i];
            my += dy[i];
        }
 
        if (mx < 0 || mx >= N || my < 0 || my >= N) continue;
        if (visited[mx][my]) continue;
        dp[x][y] += dfs(mx, my);
        visited[mx][my] = 0;
    }
    return ret;
}
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }
 
    long long ans = dfs(0,0);
    cout << ans;
    return 0;
}

또 다른 방법

// 백준알고리즘 1890번 :: 점프
#include<iostream>
using namespace std;
 
int N;
int board[101][101];
long long dp[101][101];
 
int main(void)
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }
 
    dp[0][0] = 1;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (board[i][j] == 0) continue;
            if (board[i][j] + i < N)
                dp[i + board[i][j]][j] += dp[i][j];
            if (board[i][j] + j < N)
                dp[i][j + board[i][j]] += dp[i][j];
        }
    }
 
    cout << dp[N - 1][N - 1];
 
    return 0;
}