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

Silver 2에 해당하는 문제이다. 수열의 크기와 수열을 이루는 값들이 입력되었을 때에 수열의 가장 긴 증가하는 부분 수열의 길이를 출력해야 한다.

 

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

 

[시도1] 틀렸습니다

n = int(input())
numbers = list(map(int, input().split()))
cnt = 0

for i in range(n):
  if i == 0:
    num = numbers[i]
  else:
    if num < numbers[i]:
      num = numbers[i]
      cnt += 1
    else:
      continue
  
print(cnt+1)

입력받은 numbers를 검사하면서 이전의 값과 비교해서 크면 카운트를 해주도록 코딩했는데 틀렸다... dp 개념을 사용해야 한다고 하는데.. 사실 아래의 솔루션을 아직 100% 이해하지는 못해서 하나하나 나열도 해봤지만 왜 1을 더하는지 이해하지 못했다...!

 

#솔루션

n = int(input())

numbers = list(map(int, input().split()))

dp = [1 for i in range(n)] # dp = [1] * n

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

print(max(dp))

dp는 numbers[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이를 의미한다.

dp[i] 값을 1로 초기화하고, 현재 위치 i의 원소보다 이전 위치의 원소j가 작은지 확인한다.

같거나 크면 가장 긴 증가하는 부분 수열이 될 수 없다.

그리고 현재 원소의 이전 숫자 중에서 dp 최댓값을 구하고 1을 더해준다.

 

n=6, numbers = 10, 20, 10, 30, 20, 50

 

예를 들어 i=0이면, 

i=0, 연산X

 

예를 들어 i=1이면,

i=1, j=0

numbers[1]>numbers[0] -> true / dp[1] = max(dp[1], dp[0]+1) -> 2

 

예를 들어 i=2이면,

i=2, j=0&1

numbers[2]>numbers[0&1] -> false 

 

예를 들어 i=3이면,

i=3, j=0~2

numbers[3]>numbers[0] -> true / dp[3] = max(dp[3], dp[0]+1) -> 2

numbers[3]>numbers[1] -> true / dp[3] = max(dp[3], dp[1]+1) -> 3

numbers[3]>numbers[2] -> true / dp[3] = max(dp[3], dp[2]+1) -> 3

 

예를 들어 i=4이면,

i=4, j=0&2

numbers[4]>numbers[0] -> true / dp[4] = max(dp[4], dp[0]+1) -> 2

numbers[4]>numbers[2] -> true / dp[4] = max(dp[4], dp[2]+1) -> 2

i=4, j=1&3

numbers[1]>numbers[1&3] -> false 

 

예를 들어 i=5이면,

i=5, j=0~4

numbers[5]>numbers[0] -> true / dp[5] = max(dp[5], dp[0]+1) -> 2

numbers[5]>numbers[1] -> true / dp[5] = max(dp[5], dp[1]+1) -> 3

numbers[5]>numbers[2] -> true / dp[5] = max(dp[5], dp[2]+1) -> 3

numbers[5]>numbers[3] -> true / dp[5] = max(dp[5], dp[3]+1) -> 4

numbers[5]>numbers[4] -> true / dp[5] = max(dp[5], dp[4]+1) -> 4

 

결과적으로 dp의 최댓값은 4가 된다.

 

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

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