[백준 / BOJ] 11053 가장 긴 증가하는 부분 수열

문제

출처 : www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어진다.

이때, 수열A에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다.

예를들어,

수열 : {1 2 1 4 5} 가 주어지면,

1 -> 2 -> 4 -> 5 가 가장 긴 증가하는 부분수열이되어서 답은 4이다.

 

풀이

수열의 길이가 최대 1000이므로 모든경우를 보면 시간초과가 난다.

하나의 수를 지정했을때, 다음에 올수있는 수는 999개,...998 ...997....이 되서

약 1000! 정도 반복할거라 생각했다.

 

메모리제이션을 해줘야하는데, 전에 저장된 최장 증가수열을 가져와 사용하면된다.

수열의 길이가 충분히 길지않기때문에,

0부터 자신의 idx-1까지, 자신보다 작은수를 마지막으로 하는 최장 증가수열중 가장 긴 수열을 찾아주면 된다.

자신보다 작은 범위만 반복하기때문에, 반복횟수를 나열하면,

1, 2, 3, 4, 5, 6, 7, ... , 998, 999, 1000 이 되서,

1001 * 500번 반복으로 모든경우를 다 봐줄수있다.

 

문제에서 주어진 예제1을 갖고 

위에서 말한것 처럼 dp배열을 채워보면,

예제1 )

6

10 20 10 30 20 50

 

1. idx = 1, 자신보다 작은 위치가 없다. 따라서 dp[1] = 1

2. idx = 2, 자신보다 작은위치를 본다. 이때, dp[1] = 1이고, arr[1]의값이 arr[2]보다 작으므로 dp[2] = 2

3. idx = 3, 자신보다 작은위치 1,2를 본다. 이때, arr[1], arr[2]가 모두 arr[3]보다 작지않으므로 dp[3] = 1

4. idx = 4, 자신보다 작은위치 1,2,3을 본다. 이때, arr[1], arr[2], arr[3]이 모두 자기보다 작으므로, dp[1], dp[2], dp[3]중 최댓값을 가져와 +1한다.

 

idx = 5와 idx = 6도 마찬가지로 구하면 된다.

 

수열의 길이가 충분히 길지않아서 가능한 방법이였는데, 길이가 100000정도되면 약 5억번 반복하기때문에, 다른 방법으로 풀어야한다

소스코드

https://github.com/devxb/JJUNalgo/blob/master/11053%20%EA%B0%80%EC%9E%A5%20%EA%B8%B4%20%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4/main.cpp

devxb/JJUNalgo