728x90
https://www.acmicpc.net/problem/1965
가장 기본적인 최장 거리 거리 수열 문제이다.
O(n^2)의 시간복잡도를 가지기 때문! 해당 알고리즘은 백준에 '가장 긴 증가하는 부분 수열' 시리즈를 풀어보면 좋다
현재 위치 기준으로 이전 위치들을 탐색하며 본인보다 작은게 있다면 dp 값을 최대로 업데이트 해주는 방식이다.
import sys
#from collections import deque
#import heapq
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline
if __name__ == "__main__":
n = int(input())
boxes = list(map(int, input().split()))
dp = [1 for _ in range(n)]
for i in range(n):
for j in range(i):
if boxes[i] > boxes[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 1963번 소수 경로 (0) | 2023.03.21 |
---|---|
[백준/파이썬] 5639번 이진 검색 트리 (0) | 2023.03.15 |
[백준/파이선] 24230번 트리 색칠하기 (0) | 2023.03.09 |
[백준/파이썬] 1707번 이분 그래프 (0) | 2023.03.04 |
[백준/파이썬] 1967번 트리의 지름 (0) | 2023.02.22 |