알고리즘 풀이/백준

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

배게 2018. 5. 18. 01:17
728x90

당연히 혼자 절대 못품^^


참조 : 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;
	}
}


댓글수0