[백준(baekjoon) 11053] 가장 긴 증가하는 부분 수열

문제

백준 11053

n(1…1,000)과 n의 크기를 가진 수열이 주어질 때,
수열에서 증가하는 부분 수열 중 가장 긴 길이를 출력.

• 예시 : A = {10, 20, 10, 30, 20, 50} 인 경우, A = {10, 20, 30, 50} 이고 길이는 4이다.

해결

1. 최소 길이 = 시작 값으로 끝나는 길이(초기) = 1이다.
2. for(i = 1...n-1)문을 돌며 각 값으로 끝나는 부분 수열의 최대 길이를 차례대로 구해 저장한다.
   이를 maxLength[i]라고 표현하겠다.
3. 해당 값(input[i])으로 끝나는 증가하는 부분 수열은,
   이전의 부분 수열 중 마지막 값이 자신보다 작은 경우 자신을 추가할 수 있다.
   즉, 이러한 경우 길이는 maxLength[k] + 1가 될 것다.
   for(k = 0...i-1) 차례대로 길이를 구한 후, 최대 값을 저장한다.

2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다.
최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다.

여담
해당 방식을 우선적으로 생각하긴 했지만, 시간 복잡도 계산을 제대로 하지 않고
당연히 시간초과가 뜨는 방법이라 생각했다.
그래서 O(n)이 될 수 있게 하기위해 엄청 복잡하게 각 케이스를 구하고,
나름의 방식도 찾았지만 케이스 처리를 제대로 하지 못했는지 계속 실패했다고 뜬다.

후에, 문제를 해결하고 나서 되게 허탈하긴 했지만 다음과 같은 사실을 다시 깨달았다.

1. 문제가 1시간 이상 안 풀릴땐 정답을 보자!!!!!
2. 데이터 개수가 적을 때는 시간복잡도를 우선적으로 구하자. 시간초과 날 것 같은 코드도 통과하는 경우가 수두룩하다.

알고리즘

DP로 풀었고, bottom-up 방식으로만 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.        int[][] dp = new int[n][2]; // 0 : length, 1 : last
8.        int max = 1;
9.
10.        for (int i = 0; i < n; i++) {
11.            dp[i][0] = 1;
12.            dp[i][1] = sc.nextInt();
13.            for (int j = 0; j < i; j++) {
14.                if (dp[j][1] < dp[i][1])
15.                    dp[i][0] = Math.max(dp[i][0], dp[j][0] + 1);
16.            }
17.            max = max < dp[i][0] ? dp[i][0] : max;
18.        }
19.        System.out.println(max);
20.    }
21.}

결과