[알고리즘/자바] 백준 11053번 - 가장 긴 증가하는 부분 수열

 

11053번: 가장 긴 증가하는 부분 수열

 

{8, 2 , 3 , 4} 라는 수열이 있다고 하자. 여기서 가장 긴 증가하는 부분수열을 구하면 {2,3,4}이다. 

 

처음 접근법으로는 단순하게 전수조사했다. {8,2,3,4}라는 수열이 있을때 먼저 8을 선택한 경우와 그렇지 않을 경우를 나눈다.

8을 선택하고 다음으로 가면 2가 있는데 2는 8보다 작으므로 선택할수 없다. 따라서 바로 3으로 넘어가도록 했다. 이런식으로 가장 마지막에 선택되었던 숫자를 확인하면서 아래처럼 모든 결과를 구했다. 이 방법도 나름 괜찮다고 생각했는데 결과는 시간초과.

 

이때부터 DP를 활용해야겠다고 생각했지만 구현하는데 애를 먹었다. 

{8,2,3,4}가 있을때 dp[0] = 0번째를 마지막으로 할 수 있는 LIS  , dp[1] = 1번째를 마지막으로 할수 있는 LIS로 dp를 정의했다. 근데 구현이 생각보다 잘 되지 않았다.

 

{8,2,3,4} 수열일때 dp[2]를 구하려면 어떻게 할까?? ( = 3으로 끝나는 LIS )

내가 이전에 풀었던 DP문제에선 dp[2] =  dp[1] + 어떤값 정도면 다 해결 됐었다. 

하지만 해당 문제에선 dp[2]를 구하기 위해선 dp[0] , dp[1]을 검사해서 적절한 값을 가져와야한다.

무작정 dp[1]로 dp[2]를 구하는게 아니었다. 

 

이를 통해 아이디어를 도출했는데 dp[2] = dp[0]과 dp[1] 중에서 큰값 +1 이다. 

 

 여기서 주의 할점이 있었다.

사실 dp[2]를 구하기 위해서 dp[0]을 가져와선 안된다. 0번째 숫자는 8이고, 2번째 숫자는 3이다. 우리는 증가하는 수열을 구하고 있기때문에 dp[0]을 가져오면 정답을 구할 수 없게된다. 

 

정리하면 

dp[i] = dp[0] ~ dp[i-1] 중 가장 큰값 + 1 ( 단, 0 ~ i-1번째 숫자는 i번째 숫자 보다 작은 경우만 비교대상이 될 수 있다 )

 

 

붉은 색이 dp[2]를 구하기 위해서 가져온 가장큰 dp값(=dp[1]) 

파란 색이 dp[3]을 구하기 위해서 가져온 가장큰 dp값(=dp[2])

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	
	static ArrayList<Integer> numbers = new ArrayList<Integer>();
	static int[] dp = new int[1001];
	
	public static void main(String[] args) throws IOException{
		
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		Integer.valueOf(br.readLine());
		String[] nArray = br.readLine().split(" ");
		for(int i=0; i<nArray.length; i++) {
			numbers.add(Integer.valueOf(nArray[i]));
		}
		
		int ans = lis();
		bw.write(ans + "\n");
		
		
		bw.close();
	}
	
	public static int lis() {
		
		int ans=0;
		for(int i=0; i<numbers.size(); i++){
			int maxDp = 1;
			for(int j=0; j<i; j++) {
				if(numbers.get(i) > numbers.get(j)) {
					maxDp = Math.max(maxDp, dp[j] +1);
				}
			}
			dp[i] = maxDp;
			ans = Math.max(ans,dp[i]);
		}
		
		return ans;
		

	}

		
}