문제출처 : https://www.acmicpc.net/problem/11053
1. 문제요약
- 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열은?
- A = {10, 20, 10, 30, 20, 50} 이면
A = {10, 20, 10, 30, 20, 50} 으로 길이는 4가 된다
- 1 <= N <= 1,000
- 1 <= Ai <= 1,000
2. 접근방법
- Longest Increasing Subsequence
- 초기 값
10 |
20 |
10 |
30 | 20 | 50 |
1 |
1 |
1 |
1 | 1 | 1 |
- i = 1 / 0 <= j < i
증가한다는 조건 이므로 a[i] > a[j]
현재 행에서 증가하는 부분 수열의 길이는 d[i] = max(d[i], d[j] + 1)
10 |
20(i) |
10 |
30 |
20 |
50 |
1 |
2 |
1 |
1 |
1 |
1 |
- i = 2 / 0 <= j < i
10 |
20 |
10(i) |
30 |
20 |
50 |
1 |
2 |
1 |
1 |
1 |
1 |
- i = 3 / 0 <= j < i
10 |
20 |
10 |
30(i) |
20 |
50 |
1 |
2 |
1 |
3 |
1 |
1 |
- i = 4 / 0 <= j < i
10 |
20 |
10 |
30 |
20(i) |
50 |
1 |
2 |
1 |
3 |
2 |
1 |
- i = 5 / 0 <= j < i
10 |
20 |
10 |
30 |
20 |
50(i) |
1 |
2 |
1 |
3 |
2 |
4 |
3. 시간복잡도
- n^2
4. 회고
- nlogn 방법도 있음
- https://www.youtube.com/watch?v=S9oUiVYEq7E&feature=youtu.be
- http://stack07142.tistory.com/56
소스코드
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
'먹고살려면 > boj' 카테고리의 다른 글
BOJ 11722 가장 긴 감소하는 부분 수열 (0) | 2018.01.20 |
---|---|
BOJ 11055 가장 큰 증가 부분 수열 (0) | 2018.01.20 |
BOJ 2156 포도주 시식 (0) | 2018.01.18 |
BOJ 9456 스티커 (0) | 2018.01.18 |
BOJ 2193 이친수 (0) | 2018.01.16 |