[ID: JUMPGAME] 외발 뛰기

• 문제 - https://algospot.com/judge/problem/read/JUMPGAME

algospot.com :: JUMPGAME

• 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static int T = 0;
	private static int N = 0;
	private static int[][] cache;
	private static int[][] map;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine()); // TestCase
		
		StringTokenizer st;
		for(int t = 0; t < T; t++) {
			N = Integer.parseInt(br.readLine());
			cache = new int[N+1][N+1];
			map = new int[N+1][N+1];
			
			for(int y = 0; y < N; y++) {
				st = new StringTokenizer(br.readLine());
				for(int x = 0; x < N; x++) {
					cache[y][x] = -1;
					map[y][x] = Integer.parseInt(st.nextToken());  
				}
			}
			
			int ans = jump(0, 0);
			System.out.println(ans == 1 ? "YES" : "NO");
		}
	}
	
	public static int jump(int y, int x) {
		if(y >= N || x >= N) return 0;
		
		if(y == N-1 && x == N-1) return 1;

		int ret = cache[y][x];
		if(ret != -1) {
			return ret;
		}
		
		int jumpSize = map[y][x]; 
		
		boolean ret1 = jump(y+jumpSize, x) == 1 ? true : false;
		boolean ret2 = jump(y, x+jumpSize) == 1 ? true : false;
		
		return cache[y][x] = (ret1 || ret2 == true) ? 1 : 0;
	}
}

 

• NOTE
  • Java에서는 int 자료형을 논리형으로 인식하지 못하므로 변환 과정이 필요.
  • 동적계획법 적용시, 다음과 같은 순서로 적용한다.
    1. 주어진 문제를 완전 탐색을 이용해 해결
    2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용

메모이제이션 구현 패턴

메모이제이션을 적용하기 위해서는 반드시 참조적 투명함수(referential trasparent function)여야 한다.

• 참조적 투명함수(referential transparent function)란?
  • 참조적 투명성(referential transparent)이 지켜지는 함수
  • 함수의 반환값이 입력값으로만 결정되는 함수
  • 입력이 고정되어 있을 때 그 결과가 항상 같아야 한다.

function()이 한 번 계산하는데 굉장히 시간이 오래 걸리는 참조적 투명 함수라고 가정하는 경우, 메모이제이션 구현 패턴은 아래와 같다.

1. 항상 기저 사례를 제일 먼저 처리. 입력이 범위를 벗어난 경우를 기저 사례로 처리하면 매우 유용
2. 함수의 반환 값이 항상 0이라는 점을 이용하여 cache[]를 모두 -1로 초기화. cache[]의 해당 위치에 적혀 있는 값이 -1이라면 이 값은 아직 계산이 되지 않은 값임을 의미한다. 만약 함수의 반환 값이 음수일 수 있다면 이 방법은 사용 불가.

 

 

 

참고 - 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략