Algorithm, boj, 욕심쟁이 판다(1937)

풀이

• (0,0)에서 시작하는게 아니므로 모든 지점을 돌면서 확인해 봐야한다 ( 주석처리 1번 )
• 메모이제이션 기법을 사용해야하므로 dp값이 있는 지점은 그 값을 그대로 반환한다 ( 주석처리 2번 )
• 현재 대나무 숲보다 다음 칸 대나무 숲이 더 크다면 이동하고 (+1) 그 대나무 숲에서 이동 하도록 함수를 호출해준다 ( 주석처리 2번 )
• 상,하,좌,우 네번의 이동중에 가장 큰 값을 dp값에 저장해준다. ( 주석처리 4번 )
• 해당 자리에서도 하루를 보내므로 +1일 해준다( 주석처리 5번 )

소스

package org.baekjoon;

import java.util.Scanner;

public class test1937_dp_panda {
	static int m;
	static int[][] arr, dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		arr = new int[m][m];
		dp = new int[m][m];
		for (int i=0; i<m; i++) {
			for(int j=0; j<m; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

    // 1.
		for (int i=0; i<m; i++) {
			for(int j=0; j<m; j++) {
				fun(i,j);
			}
		}
    // 5.
		System.out.println(answer+1);
	}

	static int[] nx = {-1,1,0,0};
	static int[] ny = {0,0,-1,1};
	static int answer = 0;
	public static int fun(int x, int y) {
    // 2.
		if (dp[x][y] > 0) return dp[x][y];

		for (int i=0; i<4; i++) {
			int dx = x+nx[i];
			int dy = y+ny[i];
			int newBamboo = 0;
			if (dx<0 || dx>=m || dy<0 || dy>=m)
				continue;

      // 3.
			if (arr[x][y] < arr[dx][dy]) {
				newBamboo += fun(dx, dy) + 1;
        // 4.
				dp[x][y] = Math.max(dp[x][y], newBamboo);
			}
		}
		answer = Math.max(answer, dp[x][y]);
		return dp[x][y];
	}
}

---

Reference

• 문제보러가기

---