[백준, 11053번] 가장 긴 증가하는 부분 수열

생각하는 핵심

• dp를 사용해서 현재 위치엔 조건에 만족하면서 지금까지 계산한 것들 중 가장 큰 값을 가질 수 있게 해야 함.

 

구현하기 어렵다고 생각한 부분

• 30, 10, 20, 10, 20, 60, 20, 10, 30, 50 과 같은 숫자로 구성되어 있을 경우
• 현재 위치가 60일 일때
  • 1번째 위치에 있는 10과 그 다음에 있는 20일 때 총 카운팅이 2가 될 텐데
  • 이때 다음에 있는 3번째에 있는 10과 그 다음에 있는 20의 경우에 다시 초기화를 시켜야 하나?
  • 아니면 state를 따로 두고 비교 후 변경하면서 현재 값을 조회하면서, 가장 작은 값일 때를 생각해야하나? 라고
     생각했었음.
• 아래의 코드처럼 풀게 된다면 위에처럼 복잡하게 생각할 필요없이 간단하게 풀 수 있다.
  • 우선 현재 값 전까지 현재의 값과 이전의 값들을 비교하며 현재의 값이 크다면
  • 이전의 값에 해당하는 dp의 값+1 과 현재 값에 해당하는 dp의 값을 비교 후 현재의 값에 큰 값을 넣어주기
    • 위의 코드인 dp[i] = max(dp[i], dp[j]+1) 로 인해 state를 따로 둘 필요 없이
       이전의 값이 가질 수 있는 증가하는 가장 긴 부분 수열의 수를 체크 할 수 있다.  

import sys
input = sys.stdin.readline
n = int(input())
li = list(map(int,input().split()))
dp = [1]*n
for i in range(1, n):
    for j in range(i):
        if li[i] > li[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(dp)