[백준] 욕심쟁이 판다 (java) Dynamic_programming

2020-04-03

욕심쟁이 판다 (백준> Dynamic_programming)

문제 링크

문제설명

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

예제 입력 1 복사

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

예제 출력 1 복사

4


풀이

package Dynamic_programming;

import java.util.Scanner;

public class beak_욕심쟁이판다 {
	static int arr[][];
	static int dp[][];
	static int n;
	
	public static int move(int x, int y) {
        //한군데라도 다녀왔다면 끝까지 가서 답을 가지고 있기 때문에 memoization
		if(dp[x][y] !=0)
			return dp[x][y];
		

		//기저조건에 안걸려서 for문에 들어가겠다는 뜻은 첫날이라는 뜻이다
		int dx[] = {0,0,1,-1};
		int dy[] = {1,-1,0,0};
		
        //일단 1을 넣어주고 시작하겠다
		dp[x][y] = 1;
		
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=0 && nx<n && ny>=0 && ny<n) {
				if(arr[nx][ny] > arr[x][y]) {
                    //돌아오면서 +1 해주고, 맨끝에 도달한 곳의 값은 1이다.
                    //또한, 여러 갈래에서 온 값 중 큰 값을 가져야하기때문에 Math.max()로 비교
				  dp[x][y] = Math.max(dp[x][y], move(nx,ny)+1);
				}
			}
		}
		
		return dp[x][y];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		
		arr = new int[n][n];
		
		sc.nextLine();
		
		for(int i=0;i<n; i++) {
			String s = sc.nextLine();
			String ss[] = s.split(" ");
			for(int j=0;j<n; j++)
				arr[i][j] = Integer.parseInt(ss[j]);
		}


		int answer = 0;
		dp = new int[n][n];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++)
				answer = Math.max(answer, move(i,j)); // 전부 다 돈다
		}
		

		
		System.out.println(answer);
		
	}
}

후기 (1h)

전부 다 돌아야 한다고 dfs로 풀기에는 힘들었고…

DP로 푸는 방법을 찾다가,

  1. 갈 수 있는 곳은 계속 끝까지 가면서 1로 만들고
  2. 돌아오는 길에 +1해주면서 그 값과 원래 값의 MAX를 DP값에 넣어주고
  3. Memoization을 통해, 값이 저장돼있으면 끝까지 돌지 않고, 바로 return