[Python] 11053번 가장 긴 증가하는 부분 수열

✏️ 문제

 

문제 파악

처음에는 이중 반복문을 쓸 생각을 못했어서 너무 헤맸다 ㅠㅠㅠ 얼마나 더 풀어야 다이나믹을 쉽게 풀거니!!

 

이 문제는 단순히 현재 요소에서 앞뒤 요소들과만 비교해야하는 것이 아니라 현재 요소를 기준으로 이전 모든 요소와 현재 요소를 비교해야 하는 문제이다. 

특히 기준을 맨 앞 요소로 잡으면 절대 안됨. 맨 앞 요소를 기준으로 삼는다는 말이 전혀 없기 때문!
이전의 모든 요소와 비교했을 때 현재 요소가 제일 크면 부분 수열의 요소로 추가할 수 있다.

 

문제 파악을 기준으로 풀이해보면 다음과 같다.

dp는 가장 긴 증가하는 부분 수열의 길이를 저장한다. ary[j]는 ary[i] 이전의 모든 요소를 거쳐가는 변수이다.

• ary[i] > ary[j] : 현재 요소 ary[i]가 이전 요소들보다 크다면 ary[i]는 증가하는 부분 수열의 맨 뒤 요소가 된다.
• dp[i] < dp[j] : ary[i] 이전 요소들 중 제일 큰 요소의 dp 배열값 +1 을 해야하므로 제일 큰 요소를 특정하기 위해!
• dp[i] = dp[j] : dp[j]는 이때까지 가장 긴 부분 수열의 길이
• dp[i] += 1 : 가장 긴 부분 수열에 ary[i]를 추가했으므로 부분 수열의 길이를 1 증가

 

 

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

n = int(input())
ary = list(map(int, input().split()))
dp = [0 for _ in range(n)]

for i in range(n):
  for j in range(i):
    if ary[i] > ary[j] and dp[i] < dp[j]:
      dp[i] = dp[j]
  dp[i] += 1

print(max(dp))