Gaeune's Blog-[sw expert] 3370 최장 증가 부분 수열

문제

풀이

import java.util.Arrays;
import java.util.Scanner;

public class Solution3307 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int TC = sc.nextInt();

		for (int tc = 1; tc <= TC; tc++) {
			int N = sc.nextInt();
			int[][] input = new int[2][N];
			for (int n = 0; n < N; n++) {
				input[0][n] = sc.nextInt();
			}

			for (int i = 0; i < N; i++) {
				int value = input[0][i];
				int count = input[1][i];
				for (int j = i + 1; j < N; j++) {
					if (value < input[0][j] && count + 1 > input[1][j]) {
						input[1][j] = count + 1;
					}
				}
			}
			Arrays.sort(input[1]);
			System.out.println("#" + tc + " " + (input[1][N-1]+1));
		}
	}
}

문제점 해결

처음에 최장 증가 부분 수열(LIS)의 개념을 이해하지 못해 구글링을 통해 개념을 파악했다.

LIS는 수열 N이 주어졌을 때 말그대로 가장 길게 증가하는 부분 수열을 구하는 것으로 수열 {2 1 3 2 4 5} 가 주어진다면 LIS는 {2 3 4 5} 또는 {1 2 4 5} 등으로 구해지며 답은 4가 된다.

잘못된 DP 접근 방법

처음 2중 for문 방법으로 시도했지만 시간초과라는 결과를 도출했고, 이 문제를 푼 사람들 모두 DP를 사용해 풀었다는 정보를 보게되었다. 처음 DP를 사용할 때 기준이 되는 숫자 a보다 큰 값을 가진 값들을 모두 증감연산 해주었고 해당 문제에 나와있는 테스트케이스(TC)를 기준으로 했을 땐 통과가 되었다. 하지만 실제로 코드를 실행했을 때, 10개의 TC중 단 한 개도 통과하지 못했다. 위의 TC를 기준으로 내가 시도한 방법을 적용해보면

1 3 2 4 5
-----------
0 1 0 1 1
0 1 1 1 1
0 0 0 1 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0

result: 0 0 2 1 4 5

여기서 연속되는 {0 2 4 5} 또는 {0 1 4 5}는 길이가 4가 맞지만

in		: 2 1 3 2 4 5
out		: 0 0 2 1 4 5
result1	: 2   3   4 5 (O)
result2 : 2     2 4 5 (X)
result3 :   1 3   4 5 (O)
result4 :   1   2 4 5 (O)

위와 같은 결과가 나오며 result2는 정답이 될 수 없다.

제대로 된 DP를 사용하여 풀기

			for (int i = 0; i < N; i++) {
				int value = input[0][i];
				int count = input[1][i];
				for (int j = i + 1; j < N; j++) {
					if (value < input[0][j] && count + 1 > input[1][j]) {
						input[1][j] = count + 1;
					}
				}
			}

위의 방법은 현재 값(value)이 다음 값들보다 작은지(증가하는 상태인지) 비교함과 동시에 count값을 비교해서 연속적으로 증가되는 상태인지를 파악한다.

1 3 2 4 5
-----------
0 1 0 1 1
0 0 1 0 0
0 0 0 1 1
0 0 0 0 0
0 0 0 0 1

result: 0 0 1 1 2 3

기준이 되는 값 제외 3번의 연속 증가가 발생하였으며 최종적으로 답은 4가 된다.