(Python/🥈1)백준 알고리즘 1105번:가장 긴 증가하는 부분 수열

문제 바로가기

문제 바로가기

문제 :

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력 :

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력 :

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

처음에는 

import sys

N = int(sys.stdin.readline())
lst = [int(i) for i in sys.stdin.readline().split(" ")]

dp = [0] * (N+1)
dp[1] = 1; num = lst[0]
for i in range(2, N):
    if i == 2:
        if lst[1] > num:
            dp[2] =dp[1]+1
            num = lst[1]
        else:
            dp[2] = 1
    else:
        if lst[i] > num :
            dp[i] += dp[i-1] +1
        else:
            dp[i] = dp[i-1]
print(dp[N-1])

처음에는 이런식으로 dp를 세웠다,

num에 최댓값을 저장하고 현재 인덱스가 그 num보다 큰 식으로 저장을 했다. 하지만 틀린다.

 

다시 풀어보았다.

N = int(sys.stdin.readline())
lst = [int(i) for i in sys.stdin.readline().split(" ")]

dp = [1] * N

for i in range(N):
    for j in range(i):

        if lst[i] > lst[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

 

i는 1~6까지 j는 0부터 i 까지 돌린다.

 

즉 지금 i에 인덱스에 값이 lst[i] 가 이전것들까지의 숫자들 보다 크면 list[j] dp table 값이 제일 큰 값으로 바꿔주면 된다.