[BOJ][Python][실2][11053] 가장 긴 증가하는 부분 수열

문제 링크

문제링크

첫 번째 풀이

dp[i] : arr[i]를 가장 큰 수로 가지는 가장 긴 증가하는 부분 수열의 길이

LIS는 $O(n^2)$입니다.

정답 코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
import copy

# sys.stdin = open("input.txt", "r")

n = int(input())
# R, C, K = 1, n, 1
dp = [1] * n
# dp = [[0] * C for _ in range(R)]
# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000
arr = list(map(int, sys.stdin.readline().split()))

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

print(max(dp))

잘못된 풀이

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
import copy

# sys.stdin = open("input.txt", "r")

n = int(input())
# R, C, K = 1, n, 1
dp = [0] * n
# dp = [[0] * C for _ in range(R)]
# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000
arr = list(map(int, sys.stdin.readline().split()))
max_value = arr[0]
dp[0] = 1
for i in range(1, n):
    if max_value < arr[i]:
        max_value = arr[i]
        dp[i] = dp[i - 1] + 1
    else:
        dp[i] = dp[i - 1]
print(dp[n - 1])
'''
7
1 4 5 2 3 4 5
틀린 답 3
정답 5
'''

Success Notice: 수고하셨습니다.