백준 1937번 자바

문제

https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

import java.util.Scanner;

public class Main1937_1 {

	static int n;
	static int[][] map;
	static int[][] dp;
	static int[] ax = {1,-1,0,0};
	static int[] ay = {0,0,-1,1};
	static int max;
	
	public static int dfs(int x, int y) {
		
		if (dp[x][y] != 0) {
			return dp[x][y];	
		}
		
		dp[x][y] = 1;
		
		for (int i=0; i<4; i++) {
			int nx = x + ax[i];
			int ny = y + ay[i];
			
			if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx][ny] > map[x][y]) {
				dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
			}
		}
		
		return dp[x][y];
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		map = new int[n][n];
		dp = new int[n][n];
		
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				max = Math.max(max, dfs(i,j));
			}
		}
		System.out.println(max);
	}
}

1. 조금 아쉬움이 남는 문제. 이전에 탐색했던 곳이라면 dp에 값을 저장해 풀어나가는 접근 방식을 처음에 택했다가 막히는 듯하여 다른 방법으로 삽질을 했다.

 

2. dfs만으로 풀어도 되지만 시간초과제한이 있기 때문에 dp와 같이 활용을 해야한다. 해결법 자체는 크게 어렵지 않다. 

예제 입력을 기준으로 아래의 2차원 배열이 

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

dp에선 (0, 0)에선 1 -> 상하좌우 중 갈 곳이 아무곳도 없기 때문에 1이다.

(0, 1)에선 3 -> 아래쪽으로 이동하며 (1,1)엔 2가 (2,1)엔 1이 저장된다. 

1	3
	2
	1

그렇게 되면 이후 앞쪽에서 저장된 dp배열들의 값을 활용해 최대값을 찾는 시간을 단축 시킬 수 있고 아래와 같은 dp배열이 완성 되게 된다.

1	3	1	2
3	2	3	4
2	1

1	3	1	2
3	2	3	4
2	1	4	1
3	4	1	2

 

 

정리 : 일단 문제 해결이 되긴했으나 메모리, 시간 부분을 아래 블로그의 코드와 비교를 해보니 메모리는 거의 6배, 시간은 2.5배 정도 차이가 난다. 역시 '어쨌든 작동만하면 되지'라는 마인드는 굉장히 위험하다는 것을 상기하게 된다.

왜 메모리와 시간이 이렇게까지 차이가 나는지 세세하게 비교를 해가며 공부를 해보자

 

https://rays-space.tistory.com/53