[백준/Python]1965_상자넣기

문제

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

1965번: 상자넣기

풀이

DP를 이용하여 풉니다.

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)를 찾는 문제입니다.

DP 테이블의 값은 각 열의 숫자를 포함하는 LIS의 길이를 의미합니다.

아래 표는 문제에서 주어진 예제의 DP 테이블입니다.

numbers	1	6	2	5	7	3	5	6
dp	1	2	2	3	4	4	4	5

n의 길이를 갖는 DP 테이블을 선언하고 dp[0] = 1로 초기화 합니다.

index 1 ~ (n - 1) 반복문을 돌고 임시 배열 temp를 선언합니다.

이중 반복문으로 index 0 ~ (i - 1) 까지 탐색하고 number[i]보다 number[j]가 작을 때 dp[j]를 temp에 push합니다.

탐색이 끝나면 temp의 최대 값에 1을 더한값이 dp[i]의 값이 됩니다.

단, temp가 비어있으면 number[i]가 최소값이라는 의미이므로 dp[i]는 1이 됩니다.

최종 답은 max(dp)입니다.

코드

import sys

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
dp = [0 for _ in range(n)]
dp[0] = 1
for i in range(1, n):
    temp = []
    for j in range(i):
        if numbers[j] < numbers[i]:
            temp.append(dp[j] + 1)
    if not temp:
        dp[i] = 1
    else:
        dp[i] = max(temp)
print(max(dp))