티스토리 뷰
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
N=int(input())
A=list(map(int, input().split()))
dp=[0]*N
dp[0]=1
for i in range(1,N):
max_value=0
for j in range(0,i):
if A[i]>A[j]:
max_value=max(dp[j], max_value)
dp[i]=max_value+1
print(max(dp))
|
cs |
풀이방법에 대해 긴가민가 했었는데 AC 받아서 다행이라고 느낀..문제
시간복잡도는 O(n^2) 이다.
가장 긴 증가하는 배열을 구하는 문제이다.
각 배열보다 크기가 작은 애들 중, 배열의 길이가 가장 큰 걸 뽑아서+1 해주면 구해진다.
dp(n)=(A[0]~A[n-1]<A[n] 이고 그 중 dp배열의 값이 가장 큰 애들)+1 이다.
검색해보니 더 DP 답게 푼 풀이가 다수였다.
A[n]보다 크기가 작은 배열을 만나고, dp[n]<=dp[i] 일 때마다 dp[n]에 1씩 더해준다(dp[n]은 1이라고 초기화)!
'Problem Solving' 카테고리의 다른 글
| [여름방학 프로젝트] ZeroBall(공구) (0) | 2021.07.13 |
|---|---|
| [이약저약] 초안 (0) | 2021.03.23 |
| [프로그래머스] 단속카메라 (Python3) (0) | 2021.03.03 |
| [프로그래머스] 네트워크 (Python3) (0) | 2021.03.03 |
| [BOJ 3190] 뱀 (Python3) (0) | 2021.02.24 |