문제 이해 단계
N의 길이를 가진 수열에서 최대 K개만큼 원소를 삭제할 수 있을 때,
최대한 많이 짝수끼리 연속되게 만드는 문제이다.
그때의 개수를 구하는 문제이다.
문제 접근 단계
처음에는 1차원에다가, 짝수와 홀수를 구분하여 탐색하는 BFS를 떠올렸다.
그런데 일반적인 탐색으로 하기에는
제거할 홀수의 경우의 수가 너무 많다.
그리고 그 경우의 수를 모두 체크하기엔
너무 연산이 복잡하고 또 시간이 오래 걸린다.
또한 여기서는 어떤 시작 인덱스나 숫자를 정해주지 않아서
그것 또한 찾아야 하기 때문에
이 방법은 어울리지 않는다고 생각했다.
그다음으로 떠올린 것은 다이내믹 프로그래밍이다.
왜냐하면 이런 제한시간이 짧고,
많은 경우의 수가 있는 경우에는 충분히 가능성 있기 때문이다.
연속된 짝수를 계산하기 위해, 어떤 지점 X를 체크하는 임의의 함수를 DP(X)라고 하자.
이 DP(X)는 연속된 숫자이기 때문에, DP(X-1) 또는 DP(X+1)에서 왔을 것이다.
그렇다면 한 DP(X) 간의 차이점은 무엇이 있을까?
K(현재 원소 삭제 횟수)가 있을 것이다.
이 말이 뭐냐면, DP(X,1)이란 말은
"지점 X의 삭제가 2번 남은 경우의 연속 수열 길이"를 뜻한다.
이와 함께 길이를 구해줄 length라는 매개변수를 더해줘 함수를 구성해 보자
그러면 DP(int x, int count, int length)로
구성하여 재귀함수를 구현할 수 있다.
문제에서의 예제를 시각적으로 풀어보면서 설명하겠다.
해당 인덱스 번호에서 시작하여
값이 짝수이면 Dp(x - 1, count, length + 1)
홀수면 Dp(x - 1, count + 1, length)
를 재귀함수 호출해 준다.
인덱스 번호가 1보다 작아지거나,
count가 K를 초과하거나,
홀수 움직임 때 count == K 일 때까지 반복한다.
중요한 것은 위는 하나의 연속된 수열의 길이를 구하는 것일 뿐이다.
우리는 최댓값을 구해줘야 하기 때문에, 모든 짝수에 대해서 DP를 수행해줘야 한다.
또한 0~K까지 다른 경우의 수에 대해 모두 수행해 준 다음 가장 큰 값을 구해야 한다.
자세한 것은 코드에서 설명하겠다.
문제 구현 단계
int v[1000001];
int d[50001][101];
int S, K;
int Dp(int x, int count, int length) {
if (x <= 0 || count > K) return length;
if (d[x][count] != 0) return d[x][count];
int value = 0;
if (v[x] % 2 == 0) value = Dp(x - 1, count, length + 1);
else if (count < K) value = Dp(x - 1, count + 1, length);
else if (count == K) return length;
; return d[x][count] = value;
}핵심이 되는 DP함수이다. 위에서 설명했던 매개변수를 갖는다.
그 위에는 수열의 정보를 담을 v, 연속된 길이를 담을
d[수열의 인덱스][K의 횟수]가 있다.
위에서 말했던 것처럼 범위를 벗어나면 length를 반환해 주고,
짝수일 때와 홀수일 때, 다른 재귀함수를 호출한다.
그리고 홀수면서 count == K일 때는 +1을 해줘야 하는데,
이렇게 되면 count > K 이기 때문에 초과해 버리므로 할 수 없어서 반환을 해준다.
결과적으로는 2차원 배열에 길이를 담는다.
#include <iostream>
using namespace std;
int v[1000001];
int d[50001][101];
int S, K;
int Dp(int x, int count, int length) {
if (x <= 0 || count > K) return length;
if (d[x][count] != 0) return d[x][count];
int value = 0;
if (v[x] % 2 == 0) value = Dp(x - 1, count, length + 1);
else if (count < K) value = Dp(x - 1, count + 1, length);
else if (count == K) return length;
; return d[x][count] = value;
}
int main() {
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> S >> K;
for (int i = 1; i <= S; i++) {
cin >> v[i];
}
int ans = 0;
for (int i = S; i >= 1; i--)
for (int j = 0; j <= K; j++) {
if (v[i] % 2 == 0) ans = max(ans, Dp(i, j, 0));
}
cout << ans;
}전체코드 부분이다. 밑에 반복문 부분을 유심히 보도록 하자.
모든 인덱스 번호에서 K의 모든 경우의 수를
전부 DP를 수행해 줬다. 이렇게 하면 최댓값을 찾을 수 있다.
시행착오
이 문제를 푸는데 정말 오래 걸렸다(3일)
누가 그러는데 DP는 30분 정도 잡고 있다가 안 풀리면 인터넷 참고하라고 하는데,
나는 자꾸 90%까지 올라가다가 시간초과를 맛보다 보니
여러 방법을 계속 바꿔서 했다.
그런데도 시간초과를 계속 맛봤다.
풀릴 듯 말 듯 안 풀리니까 계속 오기가 생겨서 3일까지 간 것 같다.
별의별 방법을 다 생각해 봤다.
BFS와 DP를 섞어야 하나. 아예 처음부터 잘못됐나.
그냥 답지를 볼까 했는데 자존심이 용납을 안 하고..
다행히 풀었다.
모든 K의 경우의 수를 나는 DP 내에서 돌려줬는데
이게 엄청나게 시간을 잡아먹었던 것 같다.
이걸 밖으로 빼서 돌려주니까 바로 맞았다고 뜨더라.
즉, DP 자체는 맞았는데, 부수적인 부분이 문제였던 거였다.
역시 DP 어렵네