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

헉... 건강하게 살자!

 

 

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

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

문제

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

해결방법

DP

A = {10 20 10 40 60 30 5 15}가 있다고 가정 하자 포인트는 앞에 나보다 작은 숫자가 몇개나 있는지에 대해서 이다. 가령 ind가 1일 때 20 앞에 10밖에 없으므로 10 20 으로 가장 긴 부분 수열의 길이는 2이다. 마찬가지로 ind가 5를 가정해 보자 5보다 작은 숫자는 ind가 0과 2인 10, ind가 1인 20이 존재한다. 따라서 30자리에서 가장 긴 수열은 10 20 30이 된다. 이것을 계산하는 방법은 현재 ind에서 과거의 arr값을 현재 arr값과 비교하면 된다. 그것을 아래 표와같이 표현해 보았다.

 

 

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

일단  arrVal을 받는다고 가정하자.

 

가장 쉬운 방법은 DP로 해결하는 것이다. 현재 IND를 활용하여 DP값을 유추하는 것이다. 로직은 단순한데, 현재 arrVal과 과거 arrVal을 비교하여 DP값을 계산하는 것이다.

 

DP[1]을 구하는 법은 arrVal[1]과 arrVal[0...0]까지의 값을 비교하면 된다. 만약 arrVal[0...0]보다 arrVal[1]이 크다면, DP값을 계산한다. DP[1] = max(DP[1], DP[0] + 1) DP[1] = 2로 수렴한다.

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

 

DP[2]는 arrval[2] 과 arrVal[0...1]까지의 값을 비교하면 된다. 비교하는 IND가 0일 때 arrVal[2] 는 arrVal[0]보다 크지 않기 때문에 값의 변화가 없다. arrVal[2]는 arrVal[1]보다 크지 않기 때문에 값의 변화가 없다.

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

 

DP[3]은 arrVal[3]과 arrVal[0..2]까지의 값을 비교하면 된다.

비교하는 IND가 0일 때 arrVal[3] 는 arrVal[0]보다 크기에 DP[3] = Max(DP[3], DP[0] + 1) 따라서 DP[3] = 2로 업데이트 된다.

비교하는 IND가 0일 때 arrVal[3] 는 arrVal[1]보다 크기에 DP[3] = Max(DP[3], DP[1] + 1) 따라서 DP[3] = 3로 업데이트 된다.

비교하는 IND가 0일 때 arrVal[3] 는 arrVal[2]보다 크기에 DP[3] = Max(DP[3], DP[2] + 1) 그런데 Max함수를 써보면 Max(3(DP[3], 1 + 1(DP[2]))기에 DP[3]은 업데이트 되지 않은 DP[3] = 3으로 된다.

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

... 이렇게 현재 인덱스 부터 과거의 값을 계속 바꾼다면 결국에는

 

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

가 된다.

 

이것을 코드로 작성한다면

func sola() {
    let inputLegnth = Int(readLine()!)!
    let inputArr = readLine()!.split(separator: " ").map{Int($0)!}
    
    var targetArr = Array(repeating: 1, count: inputLegnth)
    
    for i in 1..<inputLegnth {
        for j in 0...i {
            if inputArr[i] > inputArr[j] {
                targetArr[i] = max(targetArr[i], targetArr[j] + 1)
            }
        }
    }
    print(targetArr.max()!)
}
sola()

 

다음과 같이 표현할 수 있다.