[Swift_알고리즘] 백준 14002_가장 긴 증가하는 부분 수열4

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

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

문제

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

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

입력

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

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

출력

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

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

 

 

해결 방법

https://maramincho.tistory.com/40

[Swift_알고리즘] 백준 11053_가장 긴 증가하는 부분 수열

 

연장선상

IND	0	1	2	3	4	5	6	7
arrVal	10	20	10	40	60	30	5	15
DP	1	2	1	3	4	3	1	2

이렇게 DP를 정렬했다고 가정하자 

그러면 우리가 찾고싶은 수열은 {10 20 40 60}일 것 이다. 단순하게 접근해보자. DP[i] == 1, 2 ,3, 4 이런식으로 분류를 해본다고 가정해보자. 그러면 분류된 인덱스(IND)는 [0, 2, 6] , [1, 7], [3, 5], [4]가 된다. 이 값들을 적절하게 조합하기만 하면 되는데 찾고싶은 수열은 한가지 특징이 있다. 예를 들어 수열이 indSet = 1?, 2?, 3?, 4? 라고 하였을 때 "1?"는 "2?"보다 값이 작아야 한다. (인덱스도 작고 값도 작고...) 그렇게 된다면 1? < 2? < 3? <4? 라는 식이 성립하게 된다. 우리가 만약 1?부터 찾기 시작한다면 갖가지 경우의 수를 찾아야 한다. 아마 브루스트 포스가 아닐까?(자세히 생각해보지 않음...)

 

[0, 2, 6] , [1, 7], [3, 5], [4] 을 적절하게 분류하여 1?, 2?, 3?, 4?에 넣어보자.

하지만 마지막 인덱스은 4?부터 찾기 시작한다면 그 방법은 더욱 쉬울 것이다. 4?는 갯수가 1개여서 "4"만 된다. 4? = 4

3?에서는 [3, 5] 중에서 선택해야 하는데 4?값이 "4"이기에 "3"밖에 안된다. 3? = 3

2?에서는 [1, 7] 중에서 선택해야 하는데 3? 값이 "3"이기에 "1"밖에 안된다. 2? = 1

1? 에서도 역시 비슷하게 해서 2? = 0

 

이것을 코드로 표현해보면 다음과 같다.

 

func sola() {
    let inputLegnth = Int(readLine()!)!
    let inputArr = readLine()!.split(separator: " ").map{Int($0)!}

    var DP = Array(repeating: 1, count: inputLegnth)

    for i in 1..<inputLegnth {
        for j in 0...i {
            if inputArr[i] > inputArr[j] {
                DP[i] = max(DP[i], DP[j] + 1)
            }
        }
    }
    
    var flag = DP.max()!
    var resArr:[Int] = []
    for (ind, val) in DP.enumerated().reversed() {
        if val == flag {
            resArr.append(inputArr[ind])
            flag -= 1
        }
    }
    print(resArr.count)
    print(resArr.reversed().map{String($0)}.joined(separator: " "))
}
sola()

flag값을 통해 DP의 뒤쪽부터 계산해 본다.