DP - 최대 부분 증가수열

최대 부분 증가수열 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다.

 

▣ 입력설명

첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.

 

▣ 출력설명

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

 

▣ 입력예제 1

8

5 3 7 8 6 2 9 4

 

▣ 출력예제 1

4

---

🚀문제 해석

2, 7, 5, 8, 6, 4, 7, 12, 3 이 주어졌을 때, 가장 길게 증가하는 부분수열을 고려해보자.

만약 2뒤에 7을 붙이면 2 7 8 12 총 4개의 수열을 만들 수 있지만, 2뒤에 5를 붙이면 2 5 6 7 12 이렇게 최대 5개의 부분 수열을 만들 수 있다. 만약 2 5 뒤에 6을 붙이지 않고 8을 붙인다면 2 5 8 12 이렇게 4개밖에 만들지 못한다.

이렇게 생각한다면 수열의 각 숫자가 맨 마지막에 붙는 숫자라고 생각했을 때 만들 수 있는 부분수열의 길이를 고려하면 된다.

 

다시 입력 예제로 설명을 해보자.

 

5 3 7 8 6 2 9 4

 

5가 부분수열의 맨 마지막으로 온다면 길이를 어떻게 구할 수 있을까?

수열의 순서 중 5보다 아래에 있는 숫자들 중에 5보다 작은 수들만 5가 부분 수열의 맨 마지막일 때 올 수 있다.

예를 들어 1 2는 5보다 모두 작은 숫자니까 1 2 5 이렇게 올 수 있지만, 1 9 는 9가 5보다 큰 수이므로 1 5 이렇게만 올 수 있다.

따라서 5가 부분수열의 맨 마지막일 때 부분증가수열의 길이를 다음과 같이 저장할 수 있다. 일단은 아래 요소가 없으므로 1이다.

 

5 3 7 8 6 2 9 4

1

 

 

그리고 3으로 넘어가서 3 아래에 있는 숫자는 5밖에 없는데 5는 3보다 크다. 그렇기에 3이 맨 마지막일 때 부분증가수열의 길이는 1이다.

 

5 3 7 8 6 2 9 4

1

1

 

7은 5와 3보다 큰 수이다. 따라서 7이 부분증가수열의 맨 마지막에 올 때 만들 수 있는 수열은 다음과 같다.

5 7 이거나 3 7

따라서 2가 들어가게 된다.

 

5 3 7 8 6 2 9 4

1

1

2

 

8은 5, 3, 7보다 큰 수이다. 하지만 문제에서 요구하는 것은 부분증가수열의 최대길이이다.

따라서 배열에 저장된 값들 중 최댓값인 2에 8을 맨 마지막에 붙인다고 한다면 길이는 3이된다.

 

5 3 7 8 6 2 9 4

1

1

2

3

 

6은 5, 3보다 크지만 7, 8보다 작다. 따라서 7과 8이 맨 마지막에 오는 경우에는 6은 붙을 수 없다.

그렇기 때문에 2를 넣어준다. 이때 경우의 수는 5 6 이거나 3 6이다.

 

5 3 7 8 6 2 9 4

1

1

2

3

2

 

2는 자신보다 아래에 있는 모든 수열의 요소보다 작다. 따라서 1이 된다.

 

5 3 7 8 6 2 9 4

1

1

2

3

2

1

 

9는 자신보다 아래에 있는 모든 수열의 요소보다 크다. 따라서 최댓값인 3에 1을 더한 4가 들어간다.

 

5 3 7 8 6 2 9 4

1

1

2

3

2

1

4

 

마지막으로 4는 3, 2보다는 크지만 그 외에 숫자보다는 작다. 따라서 1에 1을 더한 2가 들어간다.

이때 3이 마지막으로 올때의 길이와 2가 마지막으로 올때의 길이 중에 어떤 값이 더하냐면 최댓값에 더하면 된다.

우리가 구하고 싶은 것은 부분수열의 최대길이이기 때문이다.

 

5 3 7 8 6 2 9 4

1

1

2

3

2

1

4

2

 

이렇게 완성된 배열에 담긴 요소들의 의미는 각 숫자가 맨 마지막에 올 때 부분증가수열의 길이값이다.

따라서 배열의 최댓값을 반환하면 된다.

---

코드

let [n, arr] = require('fs').readFileSync('input.txt').toString().trim().split('\n');
n = Number(n);
arr = arr.split(' ').map(Number);

function solution() {
  const dy = Array.from({ length: n }).fill(0);
  let ret = 0;
  dy[0] = 1;
  for (let i = 1; i < arr.length; i++) {
    let max = 0;
    for (let j = i - 1; j >= 0; j--) {
      if (arr[i] > arr[j] && dy[j] > max) {
        max = dy[j];
      }
    }
    dy[i] = max + 1;
    ret = Math.max(ret, dy[i]);
  }
  return ret;
}

console.log(solution());