c++) 백준 1890-점프 (dp, 재귀함수)

문제 : 1890번: 점프 (acmicpc.net)

1890번: 점프

주의할점

1. 완전탐색으로도 풀 수는 있지만, 중복되는 경우의 수를 계속해서 방문하기 때문에 시간초과가 발생할 수 있으므로, dp를 사용하여 메모이제이션을 사용해야만 한다.

2. 문제에서 경로의 개수가 최대 2^63 - 1개 라고 했으므로, int형으로 받을 수 없고

long long 또는 long long int 형을 사용해야 한다.

★출력할때 cout를 사용하면 상관없지만, printf 사용 시 꼭 %lld와 같이 알맞는 형태를 사용하자.

그렇지 않으면 영문도 모른 채 틀렸습니다를 반복하게 된다..

3. 각 칸에 주어지는 수는 0도 포함된다. 즉 재귀호출 시 주어진 숫자가 0일 경우를 처리하지 않으면

탈출할 방법이 없어서 메모리 초과 문제가 발생하게된다. 

 

풀이과정

먼저 기저사례를 정의해준다. 이 문제에서는 1. 오른쪽 끝에 도달했을 경우, 2. 범위를 초과했을 경우

두가지를 먼저 처리해주도록 하고, 그 후 메모이제이션을 사용하며,

board 값이 0일 경우에는 방법이 없기 때문에 0을 return 해주는데, cache에 0을 넣어도 되고 넣지 않아도 된다. 해당 부분에서 재귀호출이 일어나지 않기 때문이다.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
using namespace std;
int N;
int board[101][101];
long long cache[101][101];

// cache 확인하는 함수
void prin() {
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            printf("%d ",cache[i][j]);
        }
        printf("\n");
    }
}

long long solution(int y, int x) {
    // 기저사례 : 오른쪽 끝 도달
    if(y == N-1 && x == N-1) return 1;
    if(y >= N || x >= N) return 0;
    // 메모이제이션
    long long &ret = cache[y][x];
    if(ret != -1)
        return ret;
    // 칸에 0이 적혀있다면
    if(board[y][x] == 0)
        return 0;
    int jump = board[y][x];
    return ret = (solution(y+jump,x) + solution(y,x+jump));
}

int main()
{
    scanf("%d",&N);
    memset(cache,-1,sizeof(cache));
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            scanf("%d",&board[i][j]);
        }
    }
    printf("%lld\n",solution(0,0));
}