1890번-점프

문제

https://www.acmicpc.net/problem/1890

1890번: 점프

---

접근방법

1) 접근 사고

문제에서 "반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다." 라는 힌트로 두 가지의 경우로 나뉘며 재귀함수로 코드를 작성하면 구현이 쉬울 거 같은 설명이 적혀있다.

 

2) 시간 복잡도

다이나믹 프로그래밍을 활용하여 접근하였으므로 O(n)의 시간복잡도를 가진다.

 

3) 배운 점🤬이전에도 n= 100 일 때 자료형의 설정을 int 형으로 하여 오답 처리를 받은 적이 있었는데 이번에도 똑같은 실수를 했다.

인간은 똑같은 실수를 반복한다 했는데 틀린 말이 아니었다.

꼭 자료형 크기를 확인하도록 하자.

 

4) PS

자료형 크기 확인하기

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 101;
ll cache[MAX][MAX];
int board[MAX][MAX];
int n;
 
ll search(int y, int x)
{
    if(y < 0 || y >= n || x < 0 || x >= n)
        return 0;
 
    if(y == n - 1 && x == n - 1)
        return 1;
 
    if(board[y][x] == 0)
        return 0;
 
    ll &ret = cache[y][x];
 
    if(ret != -1)
        return ret;
 
    ret = search(y+ board[y][x],x) + search(y, x + board[y][x]);
    return ret;
}
 
int main(void)
{
    fastio;
    cin >> n;
 
    memset(cache, -1 , sizeof cache);
    for(int i =0; i < n; i++)
        for(int j = 0; j < n ; j++)
            cin >> board[i][j];
 
    cout << search(0,0) <<"\n";
}