BOJ_12015 : 가장 긴 증가하는 부분 수열 2
출처 : https://www.acmicpc.net/problem/12015
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
아이디어
맨 앞(0번 인덱스)보다 큰 수들을 count 시킨다. (wrong)
코드
Mine (Wrong)
import sys
input = lambda : sys.stdin.readline()
N = int(input()) #수열의 길이
A = list(map(int, input().split())) #수열
temp = 0 #현재까지 탐색된 최대 숫자값
ans = 0
for i in range(N):
if temp < A[i]:
ans += 1
temp = A[i]
print(ans)
개선사항
맨 앞(0번 인덱스)가 큰 수라면, 0번 인덱스를 포함하는 부분 수열은 최대 길이가 아니다.
ex) 50, 10, 20, 30, 40, 60
code -> [50, 60]
ans -> [10, 20, 30, 40, 60]아이디어(bisect)
Mine
import sys
from bisect import bisect_left
input = sys.stdin.readline
N = int(input()) #수열의 길이
A = list(map(int, input().split())) #수열
lis = [] #부분 수열
for num in A:
if not lis: # 초기 값 넣어주기
lis.append(num)
continue
if lis[-1] < num: # lis의 마지막(최대값)과 새로운 값 비교
lis.append(num)
else:
index = bisect_left(lis, num)
lis[index] = num
print(len(lis))
개선사항
bisect 사용법 - https://programming119.tistory.com/196
Author And Source
이 문제에 관하여(BOJ_12015 : 가장 긴 증가하는 부분 수열 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rlawlsgus117/BOJ12015-가장-긴-증가하는-부분-수열-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)