백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS)

 

 

* 문제 링크

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

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

 

 

 

문제 내용 요약

 

수열(크기 1 ≤ N ≤ 1000)이 주어졌을 때, "가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)"의 길이를 구해라

 

예) {1,2,1,3,2,5} 면 {1,2,3,5} 가 LIS 다.

 

 

 

 

접근법 (힌트에서부터 차근차근)

 

피보나치를 제외하면 가장 유명한 다이나믹 프로그래밍 문제 중 하나라고 볼 수 있을 것이다.

 

그리고 범위에 따라 푸는 방법도 달라지는 재밌는 문제라 생각한다.

 

 

 

다이나믹 프로그래밍의 기본 개념은 대충 "전에 구한 값으로 더 큰 새 값 구하기" 이다.

 

수열의 1부터 i번째까지의 값들에 대해서 i번째 값을 꼭 넣는

 

LIS 값을 m[i] 로 잡고 해보자. (다른 글에서는 dp[i]로 표현하는 경우가 많다)

 

이제 m[i+1]을 어떻게 구할 수 있을까? m[1]부터 m[i]까지 구했다고 해보자.

 

 

 

후보군을 구하는 것부터 해보자.

 

어떤 1 ≤ j ≤ i 인 j에 대해 j번째 값보다 i+1번째 값이 더 크면, m[j] + 1 이 m[i+1] 의 후보가 된다.

 

이것을 모든 1 ≤ j ≤ i 인 j에 대해 적용할 경우, 이 중에 가장 큰 값이 m[i+1] 가 될 것이다.

 

 

 

결론적으로

 

m[i+1] = max(m[i+1], m[j] + 1) when a[j] < a[i+1]

 

다음과 같이 식을 쓸 수 있고,

 

최초값은 m[0]을 0으로 놓고, 수열의 모든 값이 1 이상이므로, a[0] 또한 0으로 놓고 하던지

 

무조건 m[1] = 1 이므로 이를 가지고 해도 된다. 다만 a[1] 보다 작은 경우 m[i+1] = 1을 넣는 걸 추가해줘야 한다.

 

원하는대로 하면 된다.

 

 

 

내 코드

#include <iostream>
using namespace std;
int a[1010],m[1010];
int main() {
	int n,x=0;
	cin>>n;
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		for(int j=0;j<i;j++) {
			if(a[j]<a[i]) m[i]=max(m[i],m[j]+1);
		}
		x=max(x,m[i]);
	}
	cout<<x;
}

 

 

 

여담

 

계속 단계별로 풀어보기를 풀면서 느낀게

 

예전에 공부했던걸 까먹은 느낌이라

 

가장 기본적인 DP부터해서 문제들을 다시 되돌아보고자 하는

 

그런 목적의 첫 글이다.