[백준 11055번] 가장 큰 증가하는 부분 수열, C++, 테스트 케이스

1. 문제

---

https://www.acmicpc.net/problem/11055
 

2. 분석

---

수열의 각 원소마다 LIS의 길이를 구하고,
그 길이보다 적은 LIS를 갖는 원소들 중에서
 
나보다 값이 작은 원소 위치에서의 합을 비교한다.
이 합이 가장 큰 것을 가져와서, 내가 가진 값을 더해 내 위치의 합으로 저장한다.
 
=> 이를 위해, 각 위치에서 LIS 길이 계산하고, 가장 큰 합도 저장해두어야 한다.
 

3. 코드

---

#include <iostream>

using namespace std;

int n;

int LISRemember[1005];
int SumRemember[1005];

class Num
{
public:
	int N;
	int Len = 1;
	int Sum;
};

Num myNums[1005];

// 이분탐색으로 LIS 구하기
int binarySearch(int start, int end, int value)
{	
	while (start < end)
	{
		int mid = (start + end) / 2;
		if (LISRemember[mid] >= value)
			end = mid;
		else
			start = mid + 1;
	}

	return start;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> myNums[i].N;
		LISRemember[i] = 1005;
		SumRemember[i] = 0;
	}

	myNums[1].Len = 1;

	LISRemember[1] = myNums[1].N;	

	for (int i = 1; i <= n; i++)
	{
		int index = binarySearch(1, n, myNums[i].N);				// 현재 원소 기준 LIS 길이 index를 구한다.
		LISRemember[index] = min(LISRemember[index], myNums[i].N);	// 다음 원소 기준 LIS 길이 구하기 위해 index 길이를 LIS로 갖는 가장 작은 값을 저장한다.

		myNums[i].Len = index;										// Len은 내 원소 기준 LIS 길이이다.
		
		int k = i - 1;
		int kIndex = 0;
		int checkSum = 0;
		while (k >= 1)
		{
			if (myNums[k].Len < index)								// 나보다 LIS가 작은 원소들만 본다. 그래야 나를 포함한 LIS가 만들어질 수 있다.
			{
				if (myNums[k].N < myNums[i].N && checkSum < myNums[k].Sum)	// 나보다 값이 작으면, 그 중 가장 큰 Sum을 갖는다.
				{
					checkSum = myNums[k].Sum;
					kIndex = k;
				}
			}
			k--;
		}

		SumRemember[i] = (myNums[i].N + SumRemember[kIndex]);		// 나보다 작은 LIS를 갖는 원소 중 가장 큰 Sum을 가져와서, 내 값과 더하고 이를 저장한다.
		myNums[i].Sum = SumRemember[i];
	}

	int answer = 0;

	for (int i = 1; i <= n; i++)
	{
		answer = max(answer, myNums[i].Sum);
	}

	cout << answer;
	return 0;
}

 

4. 테스트 케이스

*2024.06.17 기준 백준에 올라온 모든 케이스를 정리했습니다.
*오류가 있는 경우 댓글 부탁드리며, 직접 테스트 케이스를 만들어보는 것도 큰 도움이 됩니다.

---

10
2 11 3 14 1 200 100 5 101 13

정답 : 228
(227이 아님.)
 

15
115 5 82 81 63 130 80 93 122 81 58 25 63 66 22

정답 : 363
 

8
1 3 5 7 2 4 6 8

정답 : 24
 

3
1 1 1

정답 : 1
(이 문제에서 동일한 값은 증가 수열에 포함X.)
 

6
1 2 3 11 4 5

정답 : 17
 

4
10 10 10 10

정답 : 10
(이 문제에서 동일한 값은 증가 수열에 포함X.)
 

5
5 1 2 3 7

정답 : 13
 

5
1 8 2 3 9

정답 : 18
 

10
5 3 8 8 2 4 8 2 3 4

정답 : 15
 

5
10 6 5 2 7

정답 : 13
 

3
52 25 34

정답 : 59
 

3
2 1 2

정답 : 3
 

5
1 7 4 3 5

정답 : 10
 

3
2 1 3

정답 : 5
 

3
20 10 15

정답 : 25
 

10
102 100 2 3 4 3 5 6 7 8

정답 : 102
 

5
5 1 2 3 10

정답 : 16
 

9
10 2 9 1 2 3 4 7 6

정답 : 17
 

4
2 6 3 4

정답 : 9
 

10
1 100 2 100 50 60 70 80 90 100

정답 : 453
 

6
5 2 10 13 21 17

정답 : 49
 

5
1000 1 2 3 4

정답 : 1000
 

6
1 3 5 2 4 6

정답 : 15
 

6
1 3 8 2 3 7

정답 : 13
 

4
30 20 10 40

정답 : 70
 

5
2 1 5 6 7

정답 : 20
 

10
1 100 2 50 60 3 5 6 7 200

정답 : 313
 

10
1 100 2 50 60 3 5 6 7 8

정답 : 113
 

5
10 90 20 80 100

정답 : 210
 

5
1 1 100 200 300

정답 : 601
 

2
1 1

정답 : 1
 

5
1 1 1 1 1

정답 : 1
 

8
100 1 2 60 50 3 6 5

정답 : 100
 

4
32 11 22 31

정답 : 64
 

7
3 2 1 2 3 4 5

정답 : 15
 

5
1 100 3 4 101

정답  : 202
 

10
100 110 90 80 70 80 90 1 2 3

정답  : 240
 

8
3 10 2 7 11 5 13 8

정답  : 37
 

10
1 100 55 50 60 3 5 6 7 8

정답  : 116