3745. 오름세 (Python)

3745번: 오름세

 

풀이

 간단하게 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)을 활용하여 해결하는 문제이다. 문제 알고리즘 자체는 어려울게 없으나 입력에 따로 종료하는 부분이 주어지지 않아 그 부분만 해결하면 된다.

 파이썬에서는 try 구문을 사용하여 exception이 발생했을 때 입력이 종료되도록 해주면 된다.

 

코드

import sys
from bisect import bisect_left
input = sys.stdin.readline

if __name__ == '__main__':
    while True:
        try:
            N = int(input())  # 주가를 관찰한 날의 수
            prices = list(map(int, input().split()))  # 관찰한 주가

            dp = [1]  # 증가하는 부분 수열의 길이를 기록해 놓는 배열. 처음에는 길이 1을 넣어놓는다.
            array = [prices[0]]  # 가장 긴 증가 부분 수열의 수들을 기록해 놓는 배열. 처음 수를 기록해 놓는다.

            for i in range(1, N):
                # 현재 주가가 들어갈 수 있는 인덱스를 찾는다.
                idx = bisect_left(array, prices[i])

                # 만약 인덱스가 현재 배열의 길이와 같다면 증가하는 부분이 새롭게 추가된다는 의미다.
                if idx == len(dp):
                    dp.append(dp[-1] + 1)  # dp 배열에는 길이를 1 증가 시킨 값을 새로 넣고
                    array.append(prices[i])  # array 배열에는 새로운 주가를 추가한다.
                else:  # 배열에 주가가 이미 존재하는 위치에 값이 들어가야 한다면
                    array[idx] = prices[i]  # 해당 위치에 있는 주가를 현재의 주가로 바꾼다.

            print(dp[-1])  # dp 배열의 가장 마지막에 있는 값이 최장 증가 부분 수열의 길이에 해당한다.
        except:  # 더 이상 입력이 없는 경우에는 break 하도록 설정
            break