[백준 3745] 오름세

문제 출처 : https://www.acmicpc.net/problem/3745

 

주식의 오름세를 찾는 문제 입니다. 점점 커지는 형태의 부분 수열을 찾는 문제로 LIS를 찾는 문제와 같습니다. LIS 라는 것만 알고 있다면 알고리즘을 이용하여 쉽게 문제를 해결 할 수 있습니다.

코드 작성

다른 함정이 없어 보이기 때문에 바로 문제를 해결해 보겠습니다. LIS를 해결할 때 속도도 빠르고 모듈을 사용하여 오류도 없을만한 이분탐색 bisect를 사용하겠습니다.

입력 받기

while True:
    try:
        N = int(input())
        arr = map(int, input().split()
    except:
        break

이 문제는 테스트 케이스의 개수가 존재하지 않습니다. 따라서 입력이 없으면 종료처리를 해야 합니다. 입력이 여러개인 문제의 경우 여러가지 해결 방안이 있겠지만 여기서는 간단하게 try except 문을 사용하겠습니다. 더 이상 입력이 없으면 예외처리로 break 문이 실행되고 while 문에서 빠져나오게 됩니다. try except 문에 대해 잘 모르겠다면 아래 링크를 통해 확인하시기 바랍니다.

https://wikidocs.net/192553

01. try except

 

다음으로 주가가 관찰된 날 N과 관찰된 주가 arr을 입력 받습니다.

LIS 구하기

다음으로 LIS를 구해보겠습니다. LIS를 구하는 방법을 잘 모르겠다면 아래 링크를 통해 LIS 구하는 방식을 확인해 보시기 바랍니다.

https://wikidocs.net/263301

07. LIS(최장 증가 수열)

 

여기서는 LIS를 구하는 다양한 방법 중 가장 효율적인 이분 탐색을 사용해서 풀어보겠습니다.

    		lis = []
        for a in arr:
            idx = bisect_left(lis, a)
            if idx != len(lis):
                lis[idx] = a
            else:
                lis.append(a)
        
        print(len(lis))

빈 리스트 lis를 만듭니다. 다음으로 arr의 원소를 하나하나 탐색합니다. 해당 값 a가 lis에 들어갈 위치를 이분 탐색인 bisect_left 함수를 통해 구합니다. idx와 lis의 길이가 같으면 a값을 lis에 추가하고, 두 값이 다르다면 idx 위치에 a를 넣어줍니다. 최종적으로 lis의 길이를 구해 그 길이를 출력할 수 있습니다.

전체 코드

전체 코드를 확인해 보겠습ㅈ니다.

from bisect import *

while True:
    try:
        N = int(input())
        arr = map(int, input().split())
        lis = []
        for a in arr:
            idx = bisect_left(lis, a)
            if idx != len(lis):
                lis[idx] = a
            else:
                lis.append(a)
        
        print(len(lis))
        
    except:
        break