[백준][Java] 1937번 욕심쟁이 판다

당연히 혼자 절대 못품^^

참조 : http://spillmoon.tistory.com/177

dp라서 점화식만 찾을 생각하다가

재귀함수를 쓴다는 것을 생각을 못했음

점화식으로 푸는 방법이 있는지조차 모르겠지만

나는 그나마 재귀로 풀이해야 코드 이해 가능한 수준임

(x,y)좌표부터 시작하여 move함수로 갈 수 있는데까지 다 돌려서

최대값을 뽑아내야함 그러기 위한 move함수 작성이 중요한데

혼자서 하려니까 절대 못했음

move함수 작성이 문제의 95프로인듯한 문제 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int N=0; static int[][] bambooInfo; static int[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); /*BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); bw.write(Integer.toString(N)); bw.flush(); bw.close();*/ dp = new int[N+1][N+1]; bambooInfo = new int[N+1][N+1]; for(int i=1; i<=N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for(int j=1; j<=N; j++) { bambooInfo[i][j] = Integer.parseInt(st.nextToken()); } } int res=0; for(int i=1; i<=N; i++) { for(int j=1; j<=N; j++) { // 4개를 돌려야함..args res=Math.max(res, move(i,j)); } } System.out.println(res); } public static int move(int i, int j) { if(dp[i][j]!=0) return dp[i][j]; int[] X = { 0, 0 , 1 , -1}; int[] Y = { 1, -1 , 0 , 0}; int nextX, nextY; int day=1; for(int d=0; d<4; d++) { nextX = i + X[d]; nextY = j + Y[d]; if(nextX>0 && nextX<=N && nextY>0 && nextY<=N) { if(bambooInfo[nextX][nextY] > bambooInfo[i][j]) { day=Math.max(move(nextX,nextY)+1, day); dp[i][j]=day; } } } return day; } }