문제출처 : 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

+ Recent posts