LIS(Longest Increasing Sequence)

최장 증가 수열.

11054 가장 긴 바이토닉 수열
https://www.acmicpc.net/problem/11054

처음으로 본 LIS 문제다.

이 문제에 처음 접근했을 땐 숫자들 중 가장 큰 숫자들의 인덱스를 찾아서 인덱스 기준 양옆으로 큰 순으로 내려가면 가장 큰 길이가 나올 것이라고 생각했다.

하지만 그렇게 풀면 가장 큰 숫자 기준으로 작은 숫자들이 있을 때 전부 더하면 연속되지도 않고

(ex - 1 < 4 < 2 < 5)

계속 밑으로 내려가면서 연속되는지 아닌지도 모른다.

(ex - 6 < 7 < 9, 8이 없다.)

그래서 두어번 정도 다 지우고 쓰기를 반복하다가, 점화식을 이용해 현재 단계(n)에서 나올 수 있는 최장 증가 수열과 전 단계(n - 1)에서 나올 수 있는 수열을 연관지을 것인지 생각하다가 질문 게시판에서 다른 사람의 코드에서 도움을 얻어 비교코드를 완성했다.

for (int i = n - 2; i > -1; i--)
    {
        for (int j = n - 1; j > i; j--)
            if (set_a[j] < set_a[i]) right_bitonic[i] = MAX(right_bitonic[i], right_bitonic[j] + 1);
    }

set_a = 입력받은 수열

right_bitonic = 수열의 인덱스 기준으로 오른쪽을 바라볼 때, 자신을 제외한 최장 연속 수열의 길이를 담은 dp 배열

저런 식으로 비교하게 된다면, i 기준으로 오른쪽에 있는 최장 연속 수열의 길이가 가장 긴 j 보다 1 큰 값을 가질 수 밖에 없게 된다. 따라서 모든 인덱스에 대해 right_bitonic 값을 구하고

마지막에 left_bitonic 값과 right_bitonic 값을 더하고 자신을 포함한 값 1을 더한 값을 출력하면 입력받은 수열에서 가장 긴 바이토닉 수열의 길이가 출력된다.

2565 전깃줄
https://www.acmicpc.net/problem/2565

정렬 + LIS를 이용해 푸는 문제였다.

처음엔 왜 LIS를 이용해야하는지 모르고 그리디를 이용해 풀었다. (사실 내가 그리디를 이용해 풀었는지도 몰랐다. 다른 사람의 코드에 대한 설명을 보다가 나와 비슷하게 풀었는데 그리디라고 설명해서 알았다.)

여기서 정렬에 대해서 다시 공부해야겠다는 생각이 들었다.

어쨋든 최장 연속 수열을 이 문제에 대입해 풀면, 최장 연속 수열이 의미하는 건 꼬이지 않고 있을 수 있는 가장 큰 조합을 의미한다. 그래서 전체 전깃줄 수에서 이 최장 연속 수열의 길이를 빼면 제거해줘야하는 전깃줄의 갯수가 나온다.

하지만 만약 코딩테스트에서 아무 사전안내 없이 풀라고 하면 내가 LIS를 떠올릴 수 있는지가 의문이다…