BOJ 11053: 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

오늘의 문제다!

---

우선 실패한 코드부터 올려보려고 한다.

n=int(input())
data=list(map(int,input().split()))
streak=[1]*n
pastScore=data
for i in range(n):
  for j in range(0,i):
    if data[i] > pastScore[j]:
      streak[j]+=1
      pastScore[j]=data[i]
print(max(streak))

우선 이 코드에서는, [1,3,2,5,4]와 같은 예시에는 접근이 불가능하다.

pastScore에 아예 data값이 들어가버리면서, 이후 더 큰 수가 와서 streak이 커지면 다시 그 큰 수 보다 작은 수가 제시되었을 때 큰 것을 인식하지 못한다.

---

성공한 코드는 다음과 같다.

n=int(input())
data=list(map(int,input().split()))
streak=[1]*(n+1)
for i in range(n):
  for j in range(i):
    if data[i]>data[j]:
      streak[i]=max(streak[i], streak[j]+1)

print(max(streak))

이 코드에서는 0부터 n-1까지 도는 i에 대해서 data[i], 그리고 0부터 i-1까지 도는 j에 대하여 data[j]를 비교한다.

이 때, data[i]가 data[j]보다 크다면, streak[i]을 업데이트할 지, 말 지를 결정할 수 있다.

이렇게 결정할 수 있는 이유는, data[i]>data[j]라는 조건이 만족될 때만 streak을 키우기 때문이다.

 

어려우면서도 할 만 한 느낌?