[Swift] 11053 - 가장 긴 증가하는 부분 수열

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

문제로 이동

문제 요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성해라.

알고리즘

1. 수열을 입력받는다.
2. 나보다 작은 수 중 부분 수열이 가장 긴 값을 찾아 저장한다.
3. result의 최댓값을 출력한다.

접근 방법

• 우선 가장 긴 증가하는 부분수열이라는 말 부터 이해를 해 보자.

  • 부분 수열 = "주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열"

  • 증가하는 수열 = "오름차순으로 증가하는 수열"

  • 가장 긴 증가하는 부분 수열 = 오름차순으로 정렬되는 부분수열 중 length가 가장 긴 수열

    -> [10, 20, 10, 30, 20, 50]에서 가장 긴 증가하는 부분 수열 = [10, 20, 30, 50]이 되는 것이다.

• 문제를 이해했으니, 문제를 푸는 방법을 곰곰히 생각해보자!

  • 우선, 원소 x에 대해 최소 부분 수열의 길이는 뭘까? -> 1이다! (x로만 이루어진 부분 수열이 있기 때문)
  • 그럼 x를 포함하는 부분 수열을 구하는 방법은 뭘까?
    • 자기 자신보다 작은 수 중 result[n]이 가장 큰 것 + 1 이 된다.
    • 즉, max( result[1...x-1] + 1, 단 x보다 작은 경우)

• 너무 추상적이니 [10, 20, 10, 30, 20, 50]으로 다시 생각해보자.

  • result 배열에는 [1, 1, 1, 1, 1, 1] 이 저장 돼 있다.
  • (10은 비교할 게 없으니 넘어간다.) 20은 10보다 크다. 따라서 10의 result에서 1을 더한 값을 갖는다.
  • 다음 3번째 원소 10을 보니, 10보다 작은 값이 전혀 없으므로 그대로 result 는 1이다.
  • 다음 4번째 원소 30을 보자. [10, 20, 10]은 모두 30보다 작다. 이 중 result가 가장 큰 것은 20이다. 따라서 30에 대한 result 값은 2 + 1 = 3이 된다. (2: 20을 포함했을 때 부분 수열, 1은 30이 포함되는 숫자)
  • 다음 20을 보자. 자기보다 작은 [10, 10] 에 대해 부분수열을 만들 수 있고, 1+1 = 2가 된다.
  • 마지막 50을 보자. 자기보다 작은 모든 값에 대해 조회하고, 가장 큰 3 + 1 = 4가 된다.

let n = Int(readLine()!)!
let numbers = readLine()!.split { $0 == " " }.map { Int($0)! }
var result = [Int](repeating: 1, count: n)
for i in 0 ..< n {
    var count = 1
    for j in stride(from: i, to: -1, by: -1) {
        if numbers[i] > numbers[j] {
            count = max(count, result[j] + 1)
        }
    }
    result[i] = count
}
print(result.max()!)