[백준] 11722번 가장 긴 감소하는 부분 수열

문제

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

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

입력

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

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

출력

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

 

이 문제가 LCD라 였나.. 그런건데.. 나는 잘 모르겠다. 아무튼 이런류의 문제의 핵심은 dp를 조작하지 않는것이 핵심이다. 이 말이 어떤 뜻인지는 계속 읽어보면 알 수도 있을것 같다.

 

10 30 10 20 20 10

 

지금 보이는 이건 예제 입력이다.  문제를 읽어보면 가장 긴 감소하는 부분이라고 한다. 이는

내림차순으로 되야 한다는 말이다.(물론 등차, 등비가 아닐 수도 있지만...ㅎㅎ)

 

이런 문제를 내가 못풀었던 가장 큰 요인은 부분 수열이라는게 무엇을 지칭하는 것인지 이해가 되지 않았다.

내가 이해하기로는 10 30 20 , 10 10 20... 이런거였다. 이것도 물론 부분 수열이 맞는데, 너무 많다고 생각해서 답을 도출하지 못했다. 지금부터 내가 이것을 해결한 방식에 대해 설명하도록 하겠다.

 

나는 이 수열하나하나를 전부 dp[i]는 1이라 생각했다. (다른 블로그들도 이렇게 작성되었긴 하지만...)   이는 dp를 조작할때, 다른 dp의 영향을 주지않겠다는 뜻이다. 그래서 위처럼 말한게 이때문이다. 물론, 이같은 해석이 잘못되있을수 도 있겠지만, 뭐 어찌되었든, 난 쉽게 이해하는걸 제공할 뿐이니... 이게 최선인것 같다. 아무튼 

10일때의 상황을 보면 앞에 아무것도 없기때문에 dp[1]은 1이다.

그다음

 

30이다. 30은 그 전 값이 10이기 때문에 값이 감소하기는 커녕 값이 증가하였다. 그렇기 때문에 틀린 답이다.

 

이렇게 하면

 

10 -> 30 10 1감소

20 -> 10 30 10 2감소 

20 -> 위와 같다.

10 -> 10 30 10 20 20 5감소...

그런데 중간중간에 중복된 숫자들이 보인다. 이 숫자들을 제거해야 할듯싶다. 왜냐하면 값이 같다는 뜻은 감소는 커녕 증가도 아니기때문이다. 그렇게 따지면 5-2는 3??? 근데... 기본값은 1이므로 4???? 도대체 답이 나오지 않는다.

이럴때 사용하는 것이 누적합이다. 그럼 무엇을 누적하냐. 여기서는 감소되는 횟수를 체크하면 된다.

누가봐도 마지막이 가장 많으므로 마지막만 하겠다.

마지막만 하겠다는건 무조건 10으로 끝내겠다는 뜻이다.

 

10 30 10 20 20 10

 

30 20 10 이렇게 2개인데 여기에 index를 넣어보자

30 10 

어차피 2번째는 1번째계산하면 답 나올 것같으니 생략한다. 가장 긴이니 안해도 될듯 싶다.

첫번째는 이렇고,  

1 2 3 4 5 6 

  30  20  10  

 

현재 이게 6번째이니 dp[6] = 1이다. 이제 하나하나 비교해가며 값을 추가해보자.

dp[6] <= dp[1] ?? 이건 2이지만... 값이 더작으므로 탈락

dp[6] <= dp[2]?? dp[2]는 2인 값으로 체크가 이미 되어있다. 그래서 값이 성립.. 또한 dp[6]는 값이 증가되었다.

그래서 dp[6] = 2

dp[6] <= dp[3] ?? dp[3]은 어차피 값이 같으므로 탈락

dp[6] <= dp[4] ?? dp[4]는  2이므로 dp[2]와 값이 같다. 값이 같다는 이야기는 dp[6] = 3

dp[6] <=  dp[5]?? dp[5]도 역시 2이다. 그런데 이미 dp[6]는 값이 증가되었기 때문에 성립되지 않는다.

 

이제 dp에는 값들이 정렬이 되어있다.

1 2 2 2 3 뭐 이런식으로 되있다. 가정하면 이 숫자들중 가장 큰 값을 선택해주면 된다.

 

이제 코드를 통해 

 

#include <bits/stdc++.h>
using namespace std;
int arr[101010];
int dp[101010];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  cin >> n;
  for(int i = 1; i<=n;i++) {
    cin >> arr[i];
  }
  
  int ans = 0;
  for(int i = 1;i <=n;i++) {
    dp[i] = 1;
    for(int j = 1; j<i;j++) {
      if (arr[i] < arr[j] && dp[i] <= dp[j]) {
        dp[i]++;
      }
    }
    ans = max(ans,dp[i]);
  }
   cout << ans;

}     

 

 

다른 사람 코드

#include <stdio.h>
#include <algorithm>
using namespace std;
int N;
int A[1003];
int LIS[1003];
int lisidx = 0;
int main(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &A[i]);
	LIS[0] = -A[0];
	lisidx = 1;
	for (int i = 1; i < N; i++) {
		if (LIS[lisidx - 1] < -A[i]) {
			LIS[lisidx++] = -A[i];
			continue;
		}
		*lower_bound(LIS, LIS + lisidx, -A[i]) = -A[i];
	}
	printf("%d", lisidx);
}

아 LCD가 아니라 LIS구나..ㅎㅎ

나중에 LIS배울때 다시 보겠구만...