백준 11053 가장 긴 증가하는 부분 수열 - python

문제

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

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

풀이

i 번째 숫자를 부분 수열에 추가할지 결정하는 세 가지 옵션이 있다.

1️⃣ 현재 구하고 있는 부분 수열에 i 번째 숫자를 넣어서 수열을 바로 증가시키거나, 혹은

2️⃣ i 번째 숫자를 선택하지 않을 수도 있다.

두 번째의 경우에 해당하는 예시는 1 / 101 / 2 / 3 / 4 / 5 이다.

1 다음에 101 을 바로 선택하는 부분 수열의 경우 이후 101보다 큰 값들이 없어서 되려 최종 개수는 2개밖에 되지 않는다. cf. 1 / 2 / 3 / 4 / 5

3️⃣ 혹은 i번째 숫자 값이 이전에 등장하 모든 값들보다 작다면, i 번째 숫자로 시작하는 새 부분 수열을 시작할 수도 있다. ex. 6 / 7 / 8 / 1 / 2 / 3 / 4 / 5

세 번째의 경우, 어차피 i 번째 이전 숫자에선 선택할 것들이 하나도 없기 때문에 i 번째 부터 다시 초기화해주어서 세는 것이다.

결국, i 번째 숫자를 선택하든지, i 번째 숫자를 선택하지 않아야한다. (인생은 결정의 연속 ! OMG)

i 번째 숫자를 선택 : 1️⃣ , 3️⃣ vs 2️⃣

그리고 1️⃣ 은 결국 제일 최적의 부분 수열 (i 번째 이전까지 쌓아올린 수열 중 길이가 제일 긴 수열) 에 i 번째 수열을 추가하겠다는 것이다.

3️⃣ = i 번째 이전 부분 수열 중 i 번째 값보다 현재 값이 작은 부분수열이 존재하지 않으므로 i 번째부터 다시 부분 수열을 시작 (차선책)

매 번째마다 각 번째 값을 포함하는 최적의 부분수열 길이를 구해주면

[1번째 값까지를 포함하는 최적의 부분수열 길이 ,2번째 값까지를 포함하는 최적의 부분수열 길이, …., ] 이렇게 담길 것이다.

이 중 최대값을 찾으면 된다.

ex. { 10 , 20 , 10 ,30 ,20 , 50}

1번째 값 (=10) 까지를 포함하는 최적의 부분 수열 길이 : 1

1번째 값 (=10) 까지를 포함하는 최적의 부분 수열 : {10}

2번째 값 (=20) 까지를 포함하는 최적의 부분 수열 길이 : 2

2번째 값 (=20) 까지를 포함하는 최적의 부분 수열 : {10,20} ;20을 포함하는 부분수열 중 최적의 선택 ! 1️⃣

그리고 1번째 값 (=10) 까지를 포함하는 최적의 부분 수열 : {10} 은 자동으로 2번째 값에서 2️⃣ 를 선택한게 된다.

3 번째 값 (=10) 까지를 포함하는 최적의 부분 수열 길이 : 1

3번째 값 (=10) 까지를 포함하는 최적의 부분 수열 : {10} ; 이전 값인 10,20 중에 10보다 작은 값은 없으므로 3번째 값을 반드시 포함하는 부분 수열은 어쩔 수 없이 3번째 값부터 다시 시작해야 함 ! 3️⃣

그리고 1번째 값 (=10) 까지를 포함하는 최적의 부분 수열 : {10} , 2번째 값 (=20) 까지를 포함하는 최적의 부분 수열 : {10,20} 은 자동으로 3번째 값에서 2️⃣ 를 선택한게 된다.

4 번째 값 (=30) 까지를 포함하는 최적의 부분 수열 길이 : 3

4번째 값 (=30) 까지를 포함하는 최적의 부분 수열 : {10,20,30} 1️⃣

{10} vs {10,20}

이런 식으로 쭉 구해진다.

코드는 다음과 같다

import sys
input=sys.stdin.readline

class LIS:
    def read(self):
        self.n=int(input())
        self.info=list(map(int,input().split()))
        
    def solve(self):
        self.sum=[]
        self.cur=[]
        for i in range(self.n):
            if i==0:
                self.sum.append(1)
                self.cur.append(self.info[0])
            else:
                    S=0
                    for j in range(len(self.sum)):
                        if self.cur[j]<self.info[i]:
                            if self.sum[j]>S:
                                S=self.sum[j]
                    self.sum.append(S+1)
                    self.cur.append(self.info[i])
                
          
        
        print(max(self.sum))
                    
lis=LIS()
lis.read()
lis.solve()