문제:
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A={10, 20, 10, 30, 20, 50}이고, 길이는 4이다.
입력:
첫째 줄에 수열 A의 크기(1<=N<=1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1<=Ai<=1,000)
출력:
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이 방법:
배열을 하나씩 커지게 만들어 가면서 증가하는 부분 수열을 찾도록 한다. 가장 큰 값을 빠르게 찾기 위해서 뒤에서 부터 값을 탐색하도록 하게 한다.
|
1
2
3
4
5
6
7
8
9
10
|
N=int(input())
idx=[1]*N
A=list(map(int,input().split()))
for i in range(N):
idx[i] = 1
for j in range(i,-1,-1):
if A[j] < A[i] and idx[j] >= idx[i]:
idx[i] = idx[j] + 1
print(max(idx))
|
cs |
문제 링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]9465. 스티커 (0) | 2019.08.24 |
|---|---|
| [BOJ]1406. 에디터 (0) | 2019.08.23 |
| [BOJ]1389. 케빈 베이컨의 6단계 법칙 (0) | 2019.08.21 |
| [BOJ]4307. 개미 (0) | 2019.08.06 |
| [BOJ]1309. 동물원 (0) | 2019.08.05 |