11053

날짜 : 2022. 11. 17

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split())) # 수열 입력
dp = [0] * n

for i in range(n):
    for j in range(i): # 앞 수열 중 본인보다 작은 원소의 개수 구하기
        # 본인보다 작은 수 구하고 그 수의 dp값이 본인 수 dp값보다 큰 경우 갱신
        if a[i] > a[j] and dp[i] < dp[j]: dp[i] = dp[j]
    dp[i] += 1 # 본인 값까지 포함하여 갱신
print(max(dp))

 

 

풀이

- 먼저 본인 값보다 작은 값을 찾는다

- 그 다음 해당 값이 저장된 인덱스의 dp값을 찾아 해당 dp값이 가장 큰 인덱스를 확인 하면서 dp값을 갱신한다

- 그리고 본인 값에 대한 dp값을 +1 하면서 최신화한다

- 해당 dp 리스트의 최댓값을 출력하면 그게 답

 

 

알게된 점

- 결과용 리스트를 만든 후 값을 push, pop하는 방식으로 진행시켰지만 처참히 틀렸다.

- 되게 풀이는 간단한데 이걸 왜 곧바로 생각해내지 못하는건지 스스로 화가 난다;;

 

 

참고 사이트

- https://pacific-ocean.tistory.com/153

[백준] 11053번(python 파이썬)