백준 11053번 가장 긴 증가하는 부분 수열 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 11053 가장 긴 증가하는 부분 수열

11053 가장 긴 증가하는 부분 수열

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

11053번: 가장 긴 증가하는 부분 수열

처음에는 그냥 set으로 중복을 없애고 길이를 출력하는 거라고 생각했다.😅 (그렇게 쉬울 리가 없다고 생각해서 이런 식으로 풀진 않았지만) 수열을 돌면서 더 큰 수가 있다면 큰 순으로 번호를 매긴다고 생각하면 된다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
dp = [1 for _ in range(n)]

for i in range(n):
  for j in range(i):
    if nums[i] > nums[j]:
      dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

---

풀이

1. nums 리스트에 수열을 받아 저장하고 길이 n 만큼의 dp 리스트도 1을 넣어 선언.
2. 두개의 for문으로 하나는 nums를 순서대로 거치고 또 하나는 i 전까지의 nums 리스트를 다시 거친다.
3. 만약 현재의 수 nums[i]가 이전 거친 수보다 큰 수가 있다면 같은 인덱스의 dp[i]를 dp[j]+1로 바꾼다.
4. max함수를 이용하는 이유는 수열의 첫번째는 1로 유지해야 하기 때문이다.
5. 이후에는 dp 리스트에서 가장 큰 수를 출력하면 된다.

---

풀이 결과

11053 풀이 결과