[백준] 1937 - 욕심쟁이 판다

[문제링크]

1937번: 욕심쟁이 판다

 

0. 메모리제이션을 이용해 동일 지점에 대한 중복연산을 피한다

  - 1-2-3-4-5 루트와 6-7-3-4-5 루트는 3-4-5가 겹치니 연산 결과를 저장, 결과가 존재하지 않을때만 사용 

 

1. 주변에 진행할 방향이 없어도 1만큼은 살 수 있으므로, cache배열은 초깃값 0을 유지

 

2. 아직 거쳐가지 않은 장소마다 rec함수로 살 수 있는 최대 년수를 확인한다

  - 검사한 모든 경로의 cache에 결과값을 저장함으로서, 재방문시 즉시 반환되도록 한다

 

3. 이미 cache가 존재하는 장소의 경우, 다른 경로의 중간 경로로서 저장된 것

  - 즉, 더 긴 결과값의 일부로서 사용됬기 때문에 무시한다

  - (사실 진입해도 즉시 반환되므로 성능상 별 영향은 없다)

 

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

public class Main{
	static int[][]map;
	static int[][]cache;
	static int max=0;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int N = pint(br.readLine());
		map=new int[N+2][N+2];
		cache=new int[N+2][N+2];
		
		for (int i = 0; i < N+2; i++) {
			map[i][0]=-1;map[i][N+1]=-1;
			map[0][i]=-1;map[N+1][i]=-1;
		}
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i+1][j+1]=pint(st.nextToken());
			}
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if(cache[i][j]==0) {
					max=Math.max(max, rec(i,j));
				}
			}
		}
		System.out.println(max);
	}
	
	static int rec(int x, int y) {
		if(cache[x][y]!=0)return cache[x][y];
		
		int temp=0;
		
		if(map[x][y]<map[x+1][y])temp=Math.max(temp, rec(x+1,y));
		if(map[x][y]<map[x][y+1])temp=Math.max(temp, rec(x,y+1));
		if(map[x][y]<map[x-1][y])temp=Math.max(temp, rec(x-1,y));
		if(map[x][y]<map[x][y-1])temp=Math.max(temp, rec(x,y-1));
		
		cache[x][y]=1+temp;
		return cache[x][y];
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면