[G1] 백준 4198번 열차정렬 C++ 다이나믹 프로그래밍, LIS, LDS, LBS

리뷰

 

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

가장 긴 바이토닉 수열 문제와 동일하다고 생각했는데, 열차 진입 순서를 고려하니 더욱 복잡해진 문제였다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• lst : 열차 중량 정보를 저장할 배열
• asc : 후미에 붙은 열차의 경우의 수를 저장할 배열
• desc : 전면에 붙은 열차의 경우의 수를 저장할 배열

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 열차 중량을 입력 받아 lst배열과 asc, desc의 초기값을 초기화한다.
2. 마지막에 들어온 열차부터 순회하며 LIS와 LDS를 각각 asc, desc배열에 초기화한다.
3. 변수 mx를 0으로 초기화 하고, LIS, LDS배열을 같이 순회한다.
4. asc, desc배열의 현재 인덱스 합에서 1을 제외한 것과 mx중 더 큰 값을 mx에 저장한다.
5. 탐색을 마친 후 mx에 저장된 값을 출력한다.

 

트러블 슈팅

1. 마지막으로 들어온 열차부터 고려해주는 것 자체에 대한 이해가 잘 가지 않아서 계속 헤딩을했다.
2. 열차가 들어온 순서대로 앞 혹은 뒤로 붙이는 형태이기 때문에 DP배열을 초기화 해줄 때 마지막 열차부터 순회해 주었어야 했다.
3. 해당 방법을 통해 LIS, LDS를 구하고, 두 배열의 동일 인덱스의 최대 합에서 중복된 피봇값을 제거해 AC를 받았다.

 

참고 사항

1. 서로 다른 두 차량의 무게가 같은 일은 발생하지 않는다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 2001;
int n;
int lst[N];
int asc[N];
int desc[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		asc[i] = 1;
		desc[i] = 1;
	}

	for (int i = n - 1; i >= 0; --i) {
		for (int j = n - 1; j > i; --j) {
			if (lst[j] < lst[i]) asc[i] = max(asc[i], asc[j] + 1);
			if (lst[j] > lst[i]) desc[i] = max(desc[i], desc[j] + 1);
		}
	}

	int mx = 0;
	for (int i = 0; i < n; ++i) {
		//cout << asc[i] << " " << desc[i] << " " << asc[i] + desc[i] - 1 << "\n";
		mx = max(mx, asc[i] + desc[i] - 1);
	}
	cout << mx;
}