[알고리즘/파이썬] 백준 11053번 - 가장 긴 증가하는 부분 수열

 

 

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

 

{ 1, 2, 1, 4, 3, 2 }라는 순열이 있을때 구할수 있는 증가 부분 수열이 몇가지 존재한다.

예를들면 [1 2] , [1 4], [1 2 3] , [1 2 4] 같은것들이다. 좌측부터 수를 뽑되(순열) 반드시 증가해야하며(증가) 주어진 순열내에 있는 숫자(주어진 순열의 부분)로 이뤄져있다.

 

위의 예시같은 경우는 3이 가장긴 부분 수열이다. ( [1 2 3] 또는 [ 1 2 4 ]인 경우 )

 

 

n = input()

# 입력받기
n_list = list(map(int,input().split()))

# 순열중 가장 좌측값을 ans에 넣는다. 
ans = [n_list[0]]

# n_list의 1번째 ~ 마지막 인덱스
for i in range(1,len(n_list)):

    # ans의 마지막값보다 n_list[i] 값이 크면 ans에 넣는다. 
    if ans[-1] < n_list[i]:
        ans.append(n_list[i])
    # ans의 마지막값보다 n_list[i]값이 작은 경우...
    else:
        # n_list[i]가 이미 ans에 있다면 pass
        if n_list[i] in ans:
            continue
        
        ans_len = len(ans)
        
        # ans를 순회한다.
        for j in range(0,ans_len):
            # ans를 순회하다가 n_list[i]보다 큰값이 나오면 
            # n_list[i]와 바꿔치기 하고 순회종료
            if ans[j] > n_list[i]:
                ans[j] = n_list[i]
                break

print(len(ans))