[실버 1] 점프

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

1890번: 점프

힌트를 봐버렸다

다이나믹 프로그래밍 나무위키를 정독해 봤다

(큰 문제를 부분 문제로 쪼개어 구하는데 부분 문제가 중복되면 기억해 주며 빠르게 처리하는 방법?) 인 듯하다

점화식을 이용하는 게 키포인트고 재귀식을 짜야 하는 옛날 기억이 난다

 

일단 마지막을 기준으로 생각해 봤다

→ ↓ 이렇게만 갈 수 있음으로 f(n, n)은 점화식으로 

f(n, n) = f(n, 0) + f(n, 1) + .....+ f(n, n-1)     +      f(0, n) + f(1, n) + ..... + f(n-1, n)

인데 문제 조건으로 해당 game_board의 값 + 해당 인덱스 = 목표 index 가 되어야 하므로

만족하는 것들만 점화식으로 더해준다

 

그리고 처음 구한 값이면 기억해 준다

 

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N;
        int[][] game_board;
        long[][] memorization;

        N = Integer.parseInt(br.readLine());
        game_board = new int[N][N];
        memorization = new long[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++)
                game_board[i][j] = Integer.parseInt(st.nextToken());
        }

 

일단 무난하게 입력받아주고

 sb.append(recursive(N - 1, N - 1, game_board, memorization));
        System.out.println(sb);

    }

    public static long recursive(int y, int x, int[][] game_board, long[][] memorization) {
        long sum = 0;

        if (y == 0 && x == 0)
            return 1;

        if (memorization[y][x] != 0)
            return memorization[y][x];

        for (int i = 0; i < y ; i++) {
            if (i + game_board[i][x] == y)
                sum += recursive(i, x, game_board, memorization);
        }

        for (int j = 0; j < x ; j++) {
            if (j + game_board[y][j] == x)
                sum += recursive(y, j, game_board, memorization);
        }

        memorization[y][x] = sum;

        return sum;
    }
}

f(0,0)은 구할 수 없으므로 1로 설정해 주고 옛날에 구했던 [y][x]면 바로 리턴

아니라면 위에서 말했던 논리대로 점화식을 짜서 구해주고 기억해 주고 값을 리턴한다

memorization 출력해 본 것