알고리즘 #14 (DP, 백준 11722번, 11053번, 11054번) [C++]

DP 4번째

 

[백준 11722번]

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

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N, MAX = 1;
	cin >> N;

	vector<int> DP(N), A(N);

	for (int i = 0; i < N; i++) {
		cin >> A[i];
		DP[i] = 1;
	}

	for (int i = 1; i < N; i++) {
		for (int j = i - 1; j >= 0; j--) {
			if (A[i] < A[j]) DP[i] = max(DP[i], DP[j] + 1);
		}
		if (MAX < DP[i]) MAX = DP[i];
	}
	cout << MAX;
}

살짝 방법찾는게 헷갈렸던 문제이다.

그럴 때는 역시 계속 써봐야ㅋㅋ

 

각각의 배열 요소에서의 감소하는 부분 수열들을 구해보면서 규칙을 찾았다. 

(배열 A는 점수, 배열 DP는 가장 긴 수열의 길이)

 

A[0] 일 때는 0만 고려한다면 DP[0] = 1,

A[1]이고 0~1만 고려할 때 만약 A[1] < A[0]라면 DP[1] = DP[0]+1,

A[2]이고 0~2만 고려해볼 때 만약 A[2] < A[0]라면 DP[2] = DP[0]+1이고 A[2] < A[1]라면 DP[2] = DP[1]+1

max() 함수로 둘 중 큰 수를 구한다.

...

 

이와 같은 방식으로 구한 DP중 가장 큰 수를 출력한다.

 

[백준 11053번]

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

11053번: 가장 긴 증가하는 부분 수열

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N, MAX = 1;
	cin >> N;

	vector<int> DP(N), A(N);

	for (int i = 0; i < N; i++) {
		cin >> A[i];
		DP[i] = 1;
	}

	for (int i = 1; i < N; i++) {
		for (int j = i - 1; j >= 0; j--) {
			if (A[i] > A[j]) DP[i] = max(DP[i], DP[j] + 1);
		}
		if (MAX < DP[i]) MAX = DP[i];
	}
	cout << MAX;
}

따로 할 건 없었다.  위의 코드와 똑같은데, A[i] > A[j] 이 부분의 부호만 바꾸어주면 된다.

 

[백준 11054번]

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

11054번: 가장 긴 바이토닉 부분 수열

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 11054
int main() {
	int N, MAX = 1;
	cin >> N;
	
	vector<int> A(N);
	vector<vector<int>> count(N, vector<int>(2, 1));

	for (int i = 0; i < N; i++)
		cin >> A[i];

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j]) {
				count[i][0] = max(count[j][0] + 1, count[i][0]);
				count[i][1] = max(count[j][0] + 1, count[i][1]);
			}
			if (A[i] < A[j]) count[i][1] = max(count[j][1] + 1, count[i][1]);
			MAX = max({ MAX, count[i][0], count[i][1] });
		}
	}
	cout << MAX;
}

각 인덱스에서 바이토닉 부분 수열의 길이의 최댓값을 저장하는 이차원 배열은 N행 2열, 1로 초기화 했다.

각각의 2행은 1, 2, 3, 4 처럼 앞으로 증가할 수열과 1, 2, 3, 2 또는 1, 2, 3, 4 등 앞으로 감소할 수열로 정했다.  

 

1. 만약 A[i] > A[j] 이라면 두 가지 경우를 생각해야 한다.

1) 증가하는 수열

2) 감소하는 수열 (A[i] = 5일 때 1, 2, 6, 5 보다 1, 2, 3, 4, 5 가 더 길 수도 있다)

 

2. 반대로 A[i] > A[j] 이라면 한 가지 경우다.

1) 감소하는 수열

 

이후 각각 최댓값을 max로 비교해 최댓값을 구한다

 

나는 이렇게 한번에 총 수열의 길이를 구했는데 다른 사람들의 코드를 보니까 증가하는 왼쪽, 감소하는 오른쪽 따로 구해서 길이를 비교하는 사람들이 많았다. 그렇게도 풀 수 있겠구나~ 했다.

 

이 문제는 푸는데 꽤 오래 걸렸다. 1시간 반정도...... 어떻게 풀어야지~ 를 대략 떠올리는 것은 그렇게 오래 걸리지 않았는데, 디테일?을 구현하는 데에서 좀 막혔다. 예를 들면 1. 2) ...ㅋㅋㅋ 연습할 때 1-2시간 이상 오래 끌지 말고 다른 사람들의 코드를 보는 것이 더 효율적이라는 것은 익히 들어 알고는 있지만.. 거의 다 구현한 것 같은데 잘 안될 때 자꾸 미련이 남아서 계속 끌게 된다ㅋ