백준_1965 상자넣기(자바) / 최장 증가 수열(LIS)

시간 & 메모리 제한

문제

문제를 읽어 보면 최장 증가 수열을 이용해야 겠다는 생각이 들었습니다.

입력 & 출력

최장 증가 수열을 이용한 문제 풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//최장 증가 수열을 구하는 문제... LIS
public class Back_1965 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int max = 0;
		
		int[] arr = new int[N+1];
		int[] dp = new int[N+1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i < dp.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= N; i++) {
			dp[i]=1;
			for (int j = 1; j < i; j++) {
				//arr[j]<arr[i] 크기가 크면 j의 dp와 비교 대상이 될 수 있다.
				//그러나 dp[i]<dp[j]+1을 통해서 이전에 이미 더 큰 갯수를 받아서 진행을 했다면
				//이 또한 걸러준다.
				if(arr[j]<arr[i] && dp[i]<dp[j]+1) {
					dp[i] = dp[j] +1;
				}
			}
			max = Math.max(max, dp[i]);
		}
		
		System.out.println(max);
	}
}

 

- 최장 증가 수열은 현재 i의 위치까지 조사를 합니다.

 

-i의 위치 전까지 처음부터 현재 위치 보다 작은 값을 조사 하며, 또한 dp의 크기 또한 비교를 해줘야 합니다.

 

- dp[i] < dp[j] +1 을 통해서 만약에 이전의 경우에서 앞으로 얻을 dp 값보다 큰 값을 획득 했다면, 값을 변경 하지 않고 진행을 하게 됩니다.

 

예를 들어 보면..

8에서 조사를 하는 경우 6일때 dp값이 5가 됩니다. 그 후에 2 의 값을 조사 했을 때, 역시 8보다 작지만, dp의 값은 6을 조사했을 때 보다 작기 때문에 값을 변경하지 않습니다.