11722

날짜 : 2022. 12. 27

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if num[i] < num[j]:  # 기존값이 비교값보다 작은 경우(감소하는 수열)
            dp[i] = max(dp[i], dp[j] + 1)  # 기존 dp 값과 비교하여 dp 값 갱신
print(max(dp))

 

 

풀이

- 이중 for 문을 활용하여 풀이한다.

- num[i]를 기준으로 한 다음 0부터 i까지 진행하는 for문을 통해 각 값들을 num[i]와 비교하면서 감소하는 수열이 적용되는 경우마다 dp값을 갱신하는 방식으로 진행한다.

 

 

알게된 점

- 이중 for문을 활용하지 않고 문제를 풀어보려 했는데 너무 복잡해졌다.

- 어차피 단순하게 생각해도 리스트 최대 길이가 1,000.

- 1,000 * 1,000 = 1,000,000 이라서 시간초과가 발생하지 않았을텐데 이중 for 문을 활용해서 풀어볼걸 조금 아쉽게 느껴진다.

 

 

참고 사이트

- https://deok2kim.tistory.com/171

[python] 백준 - 11722. 가장 긴 감소하는 부분 수열