백준 11722번 가장 긴 감소하는 부분 순열 (C++)

문제 링크이다.

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

11722번: 가장 긴 감소하는 부분 수열

 

풀면서 정답률이 이렇게 높게 나올 문제인가 하면서 자책했는데,

 

가장 긴 증가하는 부분 수열이라는 문제가 있어서 정답률이 상대적으로 높았던 것 같다.

 

 

(문제 풀이)

 

먼저 배열을 입력받고, 데이터들을 앞에 있는 모든 성분들과 비교해야 한다.

 

10 30 10 20 20 

 

위와 같이 배열이 주어졌다고 하면.

 

3번째 수인 10을 10과 30 모두와 비교하고, 20은 다시 처음부터 10, 30, 10 이런식으로 

 

이전에 나온 수들과 비교해야 한다.

 

즉 앞에서 해결한 문제가 뒤의 문제를 해결할 때 사용되기 때문에 dp라는 감을 잡고 접근하면 되겠다.

 

d[i]를 index i까지의 수를 활용해서 만들 수 있는 감소수열의 최대 길이라고 정한다.

 

확인하는 숫자가 이전 숫자보다 크다면 이전까지 나온 감소 수열의 길이에 영향을 미치지 않기 때문에 넘어가 주고, 

 

이전 숫자보다 작다면 처리를 해주면 된다.

 

길이의 최댓값을 찾고 있기 때문에, d[i]의 갱신도 최대 길이일때만 해주면 된다.

 

즉 위의 예시에서, 4번째 수인 20에 대한 처리를 한다고 해보자.

 

먼저 20은 10보다 크기 때문에 넘어간다.

 

이어서, 20은 30보다 작다 -> 30인 지점에서 감소 수열의 길이는 1이다. (엄밀히 말하면 0이라고 생각하지만 풀이의 간편성을 위해 1이라고 했다). 그렇다면 30까지의 수열과, 20이 연결되어서 수열의 길이는 1이 증가하게 되고, 수식으로 표현하면 d[20의 인덱스] = d[30의 인덱스] + 1 이다.

이것도 확정이 아니라, 만약 같은 방식으로 20보다 큰 30과 같은 수가 20의 이전에 여러개 나올 수 있는데,

d[20의 인덱스] = d[20보다 크고, 20보다 앞에 나온 수의 인덱스] + 1 이것들을 비교해서 최댓값을 d[20의 인덱스]로 결정해주면 된다.

 

#include<iostream>
using namespace std;
int d[1002];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	int arr[1002];
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= n; i++) {
		int Max = 0;
		for (int j = 0; j < i; j++) {
			if (arr[i] < arr[j]) {
				//작은 인덱스의 값보다 더 작은 값이 들어오면
				if (d[j] > Max) {
					Max = d[j];
				}
			}
		}
		d[i] = Max + 1;
	}
	
	int Max = 0;
	for (int i = 1; i <= n; i++) {
		if (Max < d[i]) {
			Max = d[i];
		}
	}
	cout << Max << '\n';
	
	return 0;
}