[백준] 11053. 가장 긴 증가하는 부분 수열 풀이 / Python, JavaScript

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

 

11053. 가장 긴 증가하는 부분 수열

기본적인 문제해결 아이디어는 다음과 같습니다.

현재 수가 V수일 때, 수열의 길이는 V보다 작은 정수들 중에서 가장 긴 수열을 가진 정수의 길이 + 1이다.

예시로 주어진 입력을 봅시다.

 

10 20 10 30 20 50

기본적으로 수열의 값을 하나씩 순회합니다. 그리고 매 순회의 결과를 담은 것을 테이블이라고 하겠습니다.

 

1. 현재 수는 10이고 10을 제외하고 지금까지 순회한 값(없음)들을 고려했을 때 10보다 작은 정수는 없습니다. 10테이블에는 0 + 1이 저장됩니다. (이는 현재 수가 10일 때, 수열의 길이가 1이라는 것을 의미합니다)

2. 현재 수는 20이고 20을 제외하고 지금까지 순회한 값(10)들을 고려했을 때 20보다 작은 정수가 있습니다. 순회한 값들에 해당하는 테이블 중에서 20보다 작으면서 가장 길이가 긴 값을 가지고 있는 테이블은 10테이블입니다. 따라서 20테이블에는 1 + 1이 저장됩니다. 

3. 현재 수는 10이고 10을 제외하고 지금까지 순회한 값(10, 20)들을 고려했을 때 10보다 작은 정수는 없습니다. 10테이블에는 0 + 1이 저장됩니다.

4. 현재 수는 30이고 30을 제외하고 지금까지 순회한 값(10, 20, 10)들을 고려했을 때 30보다 작은 정수가 있습니다. 순회한 값들에 해당하는 테이블 중에서 30보다 작으면서 가장 길이가 긴 값을 가지고 있는 테이블은 20테이블입니다. 따라서 30테이블에는 2 + 1이 저장됩니다.

5. 현재 수는 20이고 20을 제외하고 지금까지 순회한 값(10, 20, 10, 30)들을 고려했을 때 20보다 작은 정수가 있습니다. 순회한 값들에 해당하는 테이블 중에서 20보다 작으면서 가장 길이가 긴 값을 가지고 있는 테이블은 10테이블입니다. 따라서 20테이블에는 1 + 1이 저장됩니다.

6. 현재 수는 50이고 50을 제외하고 지금까지 순회한 값(10, 20, 10, 30, 20)들을 고려했을 때 50보다 작은 정수가 있습니다. 순회한 값들에 해당하는 테이블 중에서 50보다 작으면서 가장 길이가 긴 값을 가지고 있는 테이블은 30테이블입니다. 따라서 50테이블에는 3 + 1이 저장됩니다.

7. 모든 수를 순회했고 테이블에서 가장 큰 값은 50테이블의 4입니다.

 

점화식은 아래와 같습니다.

table[i] = max(i 미만의 table) + 1

 

작성 코드 (.py)

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
table = [0] * (max(arr) + 1)
for v in arr:
    table[v] = max(table[:v]) + 1
print(max(table))

작성 코드 (.js)

function solution(n, arr) {
  const table = Array(Math.max(...arr) + 1).fill(0);
  arr.forEach((v) => {
    table[v] = Math.max(...table.slice(0, v)) + 1;
  });
  return Math.max(...table);
}
solution(6, [10, 20, 10, 30, 20, 50]);