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

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

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

 

스터디중 25분내에 풀지 못하고 곤혹에 빠졌던 문제이다. 

dp를 이용하여야 하는 문제이다. 

 

정답 코드 먼저!!!!

 

n = int(input())
l = list(map(int, input().split()))

dp = [1] * (n + 1)
for i in range(1, n) :
  for j in range(i) :
    if l[i] > l[j] :
      dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

코드는 간단하다.

 

접근 방식

1. 배열을 순회한다. 이때 자기 자신 이전까지의 값을 체크하면서 자기보다 작은 값이 있다면  그 값이 가진 길이에 대한 값과 비교를 실시한다.
2. 여기서 dp가 들어와야 한다. 현재 설정된 값과 새로 들어올 값을 비교해주어야 한다.
   1. 10 20 10 30 으로 가정하고 현재 index가 30이라 가정하겠다. 
   2. 20을 순회했을때는 2일거고 그 다음 10일때는 1이다
   3. 30을 순회했을때 20을 순회하면 값이 3이 될거다. 그런데 다음 10을 순회할때 값의 갱신을 막아주어야 한다.
   4. 10을 순회할때 이미 이전에 20으로 인해 설정된 값과 비교를 해서 더 큰 값을 설정해주어야 로직에 오류가 없다.
   5. 두 번째 10과 비교를 할때 dp개념이 들어온다!! (쉽게 떠오르지 않았던 부분)

 

애를 먹었던 부분

1. 모든 배열의 최소 증가 길이는 1이다. 0으로 설정을 해줘서 값이 다르게 나왔던 우여곡절이 있다.