[JAVA] BOJ(백준) - 가장 긴 증가하는 부분 수열 - 11053

문제 내용

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

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

---

문제 접근 방법

먼저 LIS에 대해 알아야 한다.

문제에서 예시로 {10, 20, 10, 30, 20, 50} 일경우 LIS는 {10, 20,  ,30,  ,50} 이된다. 즉, LIS의 길이는 4이다.

한가지 예시를 더 들면 {10, 20, 40, 25, 20, 50, 30, 70, 85} 일경우 LIS는 {10, 20, 40,  ,  ,50 ,  , 70, 85} 가 된다. 즉, LIS의 길이는 6이 된다.

 

예시를 보면 알겠지만 LIS는 첫번째 원소부터 시작해 현재 원소값이 이전 원소값보다 큰 값이라면 LIS 수열에 현재 원소값을 추가해서 증가하는 부분 수열을 만드는 것이라고 볼 수 있다.

이 부분을 통해 이 문제는 현재 원소값을 기준으로 이전 원소값과 비교하고 길이를 증가시킬지 말지 결정하면 되는 문제이다.

 

이때 dp배열을 'dp[현재 원소값의 인덱스] = 현재 원소값까지 부분수열의 길이' 로 정의 한다면.

입력받은 A배열 = {10, 20, 10, 30, 20, 50} 일때

dp[0] = 1 이고 LIS는 {10} // A는 {10}

dp[1] = 2 이고 LIS는 {10, 20} // A는 {10, 20}

dp[2] = 2 이고 LIS는 {10, 20} // A는 {10, 20, 10}

dp[3] = 3 이고 LIS는 {10, 20, 30} // A는 {10, 20, 10, 30}

dp[4] = 3 이고 LIS는 {10, 20, 30} // A는 {10, 20, 10, 30, 20}

dp[5] = 4 이고 LIS는 {10, 20, 30, 50} // A는 {10, 20, 10, 30, 20, 50} 이라고 할 수 있다.

 

이를 말로 풀어서 설명하자면 현재 원소값의 인덱스가 3일때 A의 원소값은 30이 되고,

30 이전 원소값들인 {10, 20, 10} 을 하나씩 비교해가며 30이 더 클땐 부분수열을 추가해주면 된다.

이때 주의할점은 그냥 무작정 추가하면 안되고, 이전에 메모제이션된 dp값들과 하나씩 같이 비교하고 추가해야 한다. 즉

dp[3]<=dp[0] 이라면 dp[3] = dp[0] + 1

dp[3]<=dp[1] 이라면 dp[3] = dp[1] + 1

dp[3]<=dp[2] 라면 dp[3] = dp[2] + 1

로 해야한다.

 

말로하는데 한계가 있으니 풀이를 보고 이해해보자.

풀이를 보고 모르겠다면 하나씩 출력해가면서 이유를 생각해보는것도 추천한다.

 

 

---

풀이

BottopUp

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

public class Main {
	static int[] A; //입력받는 값
	static int[] dp; //dp[현재 인덱스 위치 <- 부분수열의 길이] = LIS(길이)
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = new int[n];
		dp = new int[n];
		
		for(int i=0; i<n; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		//첫번째 원소일때 부분수열은 원소가 하나라서 무조건 길이가 1임.
		//1로 초기화
		dp[0] = 1;
		
		//첫번째 원소를 제외한 부분수열의 길이가 i일때 LIS를 찾기위함.
		for(int i=1; i<n; i++) {
			dp[i]=1; //부분수열의 길이는 최소 1이상임. 초기화.
			for(int j=0; j<n; j++) {
				//n번째 원소를 이전 원소들과 하나씩 비교해서 더 클때마다
				//n번째 원소의 dp초기값 1에서 1씩 증가시켜줘야 최장부분수열이 나옴.
				//단, dp에 저장된 값중 이전 원소값보다 더 크다면 이미 n번째 까지는 다 증가 시킨것으로
				//더 이상 증가 안시켜줘도됨.
				if(A[j]<A[i] && dp[i]<=dp[j]) {
					dp[i] =dp[j]+1;
				}
			}
		}
		
		int max = Integer.MIN_VALUE;
		for(int x:dp) {
			max = Math.max(max, x);
		}
		System.out.println(max);
	}
}

 

TopDown

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

public class Main {
	static int[] A;
	static int[] dp;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = new int[n];
		dp = new int[n];
		
		for(int i=0; i<n; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		dp[0] = 1;
		
		//현재값이 0일때부터 n-1까지 그때그때 LIS의 길이를 구함
		for(int i=0; i<n; i++) {
			LIS(i);
		}
		
		int max = Integer.MIN_VALUE;
		for(int x:dp) {
			max = Math.max(max, x);
		}
		System.out.println(max);
	}
	
	public static int LIS(int n) {
		if(dp[n]==0) {//계산 안됐다면 ㄱㄱ
			dp[n] = 1;//초기화
			for(int i=n-1; i>=0; i--) {//n이전 원소값들 탐색
				if(A[n]>A[i]) {
					//이전 dp값+1과 현재 dp값을 비교 후 할당
					dp[n]=Math.max(LIS(i)+1, dp[n]);
				}
			}
		}
		return dp[n];
	}
}

 

---

마치며

BottomUp으로 풀때 이중포문에서 j는 0~n-1까지로 해놨는데 0~i로 바꿔도 상관없다.

어차피 현재값기준으로 이전값들과 비교하는 것이기 때문에 뒤에값은 별 필요없기 때문!

그리고 이문제는 조건을 주는 부분이 가장 어렵지만 조건을 어떻게 줄지 알수만 있다면 쉽게 풀리는 문제라고 생각한다.