백준 11722번 가장 긴 감소하는 부분수열 - C++

문제

---

수열 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의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

 

문제 링크

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

 

 

풀이

---

다이나믹 프로그래밍을 사용하면 되는 문제다.

다이나믹 프로그래밍을 사용하면 쉽게 풀린다는 것은 문제를 보고 바로 알았지만 시행착오가 조금 있었다.

 

우선 잘못된 접근부터 보자.

 

잘못된 접근

풀이

가장 처음에 했던 접근은 거꾸로 올라가며 이전보다 값이 크면 증가된 값을 기록하는 방식으로 했다.

예를 들어 아래와 같이 값이 들어왔다고 해보자.

 

$10, 30, 10, 20, 20, 10$

 

그러면 가장 마지막에 있는 값인, 인덱스 5의 $10$부터 확인에 들어간다.

$10$에서 시작한다고 가정했을 때 만들 수 있는 가장 큰 감소하는 부분 수열은 당연히 1이기에 우선 DP에 1을 적어준다.

 

$DP Table = {0, 0, 0, 0, 0, 1}$

 

그 다음엔 인덱스 4의 $20$을 본다.

이전 값인 인덱스 5의 $10$보다 크니, DP Table에는 2가 들어가게 된다.

이전까지 만들어진 가장 큰 감소하는 부분수열에 현재의 값만 앞에 붙여주면 그 다음으로 가장 큰 감소하는 부분수열이 만들어지는 셈이기 때문이다.

 

그리고 이 과정을 반복해주었다.

 

$DP Table = {3, 3, 2, 2, 2, 1}$

 

이러면 예제는 통과할 수 있게 된다.

 

문제점

그러나 문제점이 있었으니, 값이 아래와 같이 들어오게 되면 예외가 발생하게 된다.

 

$4, 3, 2, 3, 2, 1$

 

인덱스 2의 $2$까지는 순조롭게 진행되지만, 인덱스 3의 $3$을 만나게 되면 값이 꼬이게 된다.

실제로 만들 수 있는 가장 큰 감소하는 부분수열은 3이지만 이전 값보다 증가한다는 이유로 하나 더 증가시켜 4가 나오고, 최종에는 5가 된다.

 

$Wrong DP Table = {5, 4, 3, 3, 2, 1}$

$Correct DP Table = {4, 3, 3, 3, 2, 1}$

 

올바른 접근

그러면 올바른 접근은 무엇인가?

가장 앞에서부터 하나씩 값을 비교하며 작은 값이 나오면 증가는 시켜주되, 지금까지 나온 값들에 대해 모두 검증을 받는 것이다.

아까는 뒤에서부터 했는데, 이러면 인덱스 값 계산이 어려워져서 앞에서부터 확인하는걸로 바꿨다.

뒤에서부터 하나 앞에서 하나 똑같은데, 인덱스 계산만 어려워지기에 앞에서하는걸로 결정했다.

 

값이 이렇게 들어왔다고 하자.

 

$10, 30, 10, 20, 20, 10$

 

우선 인덱스 0의 $10$의 DP값은 1이다.

 

$DP Table = {1, 0, 0, 0, 0, 0}$

 

그 다음에 인덱스 1의 $30$을 보자.

이전 값들을 쭉 확인해봤을 때, 자신보다 큰 값이 없기에 그대로 1이 들어간다.

 

$DP Table = {1, 1, 0, 0, 0, 0}$

 

그 다음으로 인덱스 2의 $10$을 보자.

이전 값들을 쭉 확인해봤을 때, 자신보다 크면서 DP값에 1을 더했을 때 증가하는 값인 인덱스 1의 $30$이 있기에 2를 넣어준다.

 

$DP Table = {1, 1, 2, 0, 0, 0}$

 

이를 계속 반복해준다.

$DP Table = {1, 1, 2, 2, 0, 0}$

$DP Table = {1, 1, 2, 2, 2, 0}$

$DP Table = {1, 1, 2, 2, 2, 3}$

 

이러면 최종적으로 가장 큰 값으로 3이 나오게 되어 예외 없이 답이 나오게 된다.

 

 

C++ 코드

---

#include <iostream>
#include <utility>

using namespace std;

int N;
int number[1001];
int DP[1001];
int maxValue;
int answer;

void input() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> number[i];
  }
}

void solve() {
  DP[N - 1] = 1;
  maxValue = number[N - 1];

  if (N == 1) {
    answer = 1;
    return;
  }

  for (int i = 0; i < N; i++) {
    DP[i] = 1;
    for (int j = 0; j < i; j++) {
      if (number[j] > number[i] && DP[j] + 1 > DP[i]) {
        DP[i] = DP[j] + 1;
      }
    }
  }

  for (int i = 0; i < N; i++) {
    answer = max(answer, DP[i]);
  }
}

void output() {
  cout << answer;
}

int main() {
  input();
  solve();
  output();
}