[파이썬] 11053 가장 긴 증가하는 부분 수열

최근에 조금 놀았다

 

그래도 하루에 한 문제는 풀고 놀았다...

 

물론 그게 유익한 풀이라고는 할 수는 없으나 

 

적어도 습관을 유지하기 위해서는 꼭 한 문제는 풀어야 한다는 생각..

 

새벽에 dp나 하나 풀어보자! 해서 단계별 학습에 있는 dp문제를 하나 가져왔다

 

LIS라 불리는 문제인 듯한데.. 유명한듯하다 

처음 문제 딱 봤을 때는

 

?? 이거 그냥 배열로 풀면 풀리는 거 아니냐

 

해서 질문게시판에 있는 반례 몇 개와 돌려봤더니

 

역시 틀렸다

 

문제를 살짝 잘못 이해하고 있었다 

 

5
40 1 5 10 90

 

문제의 예제와 이 반례를 생각하면 쉽게 풀릴 것 같다

 

증가하는 부분 배열이니

 

중간에 끊기는 건 상관없으나 제일 처음에 잘리는 수는 빼야한다! 를 깨달았다 

 

사실 여기까지는 생각해냈는데 

 

dp를 어떻게 이용해서 풀어야할지 막막했다

 

여태 푼 dp 기초들은 그냥 냅다 ary값에 더 해온 값을 참조해서 마지막 값을 이끌어냈는데

 

이건 부분이라서 무작정 더해도 안될 것 같고..

 

결국 한 30분 고민하다가 구글에 쳐봤다..

 

보니 배열을 하나 더 주고 카운팅을 하면서 올라가는 기법을 다들 썼다

 

오우야 ;; 

 

코드를 보자

 

n=int(input()) ary=list(map(int, input().split())) dp=[1]*n for i in range(1,n):   for p in range(i):     if ary[p]<ary[i]:       dp[i]=max(dp[i],dp[p]+1) print(max(dp))

수를 담은 ary와

 

카운트를 담을 dp배열을 만든다 

 

그리고 배열을 돌면서 ary[i]의 뒤에 있는 숫자들을 비교하면서

 

크면 dp배열을 참조하여 더하고 넣는다

 

....

 

dp문제를 풀 때마다 생각하는 거지만

 

진짜 답을 보면 허무해진다

 

이걸 왜 생각을 못한 것인가

 

머리가 부족한 건지.. 아니면 재치가 부족한건지 ..

 

새벽에도 이마빡을 팍! 치며 감탄하며 문제를 푼다