• 출처 : https://www.acmicpc.net/problem/11054

• 알고리즘 : DP, LIS

• 풀이

  1. 모든 수열을 돌면서
  2. 현재 원소가 기준 값일 때 증가하는 최장 길이를 구한다
  3. 감소하는 최장 길이는 reversed로 똑같이 구현

• 소감

  • 처음에 보고 엄청 막막했다가 LIS 문제 복잡도 NlogN에서 한 바퀴만 더 돌면 될 것 같아 시도해봤다.
  • 다행히 python3에서도 성공!

코드

# O((N^2)logN)

def 최장길이(수열):
    증가리스트 = []
    for 현재위치 in range(len(수열)):
        현재값 = 수열[현재위치]
        최소위치 = 최소위치찾기(증가리스트, 0, len(증가리스트)-1, 현재값)
        if 최소위치 < len(증가리스트):
            증가리스트[최소위치] = 수열[현재위치]
        else:
            증가리스트.append(수열[현재위치])
    return len(증가리스트)


def 최소위치찾기(리스트, 시작, 끝, 현재값):
    if 시작 > 끝:
        return 시작
    중간 = (시작+끝)//2
    if 리스트[중간] >= 현재값:
        return 최소위치찾기(리스트, 시작, 중간-1, 현재값)
    else:
        return 최소위치찾기(리스트, 중간+1, 끝, 현재값)


def 초기화():
    전체길이 = int(input(''))
    수열 = list(map(int, input('').split(' ')))
    return 전체길이, 수열, float('-inf')


전체길이, 수열, 최대길이 = 초기화()
for i in range(전체길이):
    증가수열 = 수열[:i+1]
    감소수열 = list(reversed(수열[i:]))
    증가길이 = 최장길이(증가수열)
    감소길이 = 최장길이(감소수열)
    최대길이 = max(최대길이, 증가길이+감소길이-1)
print(최대길이)