[백준 1937] 욕심쟁이 판다

문제 출처

사용 언어: Java

1. 구상

• LIS 알고리즘 이용.

• 상하좌우를 관리하는 배열 생성.

• 현재 위치에서 상하좌우의 LIS를 구하고 최종적으로 최대값을 구하기.
  
  

2. 구현

import java.util.*;
import java.io.*;

public  class Main {
	
	public static int[][] forest;
	public static int[][] dp;
	public static int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 
	public static int total;
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);
		
		total = s.nextInt();
		forest = new int[total][total];
		dp = new int[total][total];		
		
			
		for (int i = 0; i < total; i++) {
			for(int j = 0; j < total; j++) 				
				forest[i][j] = s.nextInt();
		}
		
		for (int i = 0; i < total; i++) {
			for(int j = 0; j < total; j++) {				
				LIS(i, j);
			}


		}
		
		int max = 0;
		
		for (int i = 0; i < total; i++) {
			for(int j = 0; j < total; j++)
				max = Math.max(max, dp[i][j]);			
		}
		
		System.out.println(max);
		
				
	}
	
	public static int LIS(int i, int j) {				
		
		//탐색했는지 확인하기
		if (dp[i][j] == 0)  {
			dp[i][j] = 1;
			
			for (int x = 0; x < 4; x++) {
				int MoveI = i + move[x][0];
				int MoveJ = j + move[x][1];
				if (MoveI >= 0 && MoveI < total && MoveJ >= 0 && MoveJ < total && forest[i][j] < forest[MoveI][MoveJ])
					dp[i][j] = Math.max(dp[i][j], LIS(MoveI, MoveJ) + 1);			
				

			}
			
			
		}	
		
		return dp[i][j];
		
		}
	
	
} 

- 기존의 LIS 알고리즘을 변형하여 이용.

- 현재 위치에서 상하좌우로 이동한 좌표를 이용하여 현재값보다 크면 LIS 알고리즘 적용.