22857번 : 가장 긴 짝수 연속한 부분 수열 (small)
문제)
길이가 인 수열 가 있다. 수열 는 1 이상인 정수로 이루어져 있다.
수열 에서 원하는 위치에 있는 수를 골라 최대 번 삭제를 할 수 있다.
예를 들어, 수열 가 다음과 같이 구성되어 있다고 가정하자.
수열 S : 1 2 3 4 5 6 7 8수열 에서 4번째에 있는 4를 지운다고 하면 아래와 같다.
수열 S : 1 2 3 5 6 7 8 수열 에서 최대 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.
입력 :
수열 의 길이 와 삭제할 수 있는 최대 횟수인 가 공백으로 구분되어 주어진다.
두 번째 줄에는 수열 를 구성하고 있는 개의 수가 공백으로 구분되어 주어진다.
출력 :
수열 에서 최대 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
풀이)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<int> vec;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
vec.resize(n);
for (auto& ele : vec)cin >> ele;
int s = 0;
int e = 0;
int ans = 0;
int odd = 0;
int even = 0;
while (e < n)
{
if (odd <= k)
{
if (vec[e] % 2)
{
odd++;
}
else
{
even++;
ans = max(ans, even);
}
e++;
}
else
{
if (vec[s] % 2)
{
odd--;
}
else
{
even--;
}
s++;
}
}
cout << ans;
return 0;
}
|
cs |
탑다운 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
// 22857. 가장 긴 짝수 연속한 부분 수열 (small)
#include <iostream>
#include <vector>
using namespace std;
int n, k;
vector<int> vec;
int dp[50010][109];
int recur(int cur, int cnt)
{
if (cur == n || cnt == k + 1) return 0;
int ret = 0;
if (dp[cur][cnt] != -1) return dp[cur][cnt];
if (vec[cur] % 2 == 0) // 짝수일 경우
{
ret = max(ret, recur(cur + 1, cnt) + 1);
}
else // 홀수일 경우
{
ret = max(ret, recur(cur + 1, cnt + 1));
}
dp[cur][cnt] = ret;
return dp[cur][cnt];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
vec.resize(n);
for (auto& ele : vec) cin >> ele;
fill(&dp[0][0], &dp[50009][109], -1);
int ans = 0;
for (int i = 0; i < n; i++)
{
ans = max(ans, recur(i, 0));
}
cout << ans;
return 0;
}
|
cs |
출처 : https://www.acmicpc.net/problem/22857
22857번: 가장 긴 짝수 연속한 부분 수열 (small)
수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.
www.acmicpc.net
'Develop > 백준 (Cpp)' 카테고리의 다른 글
| [백준] 21313번 : 문어 (C++) (0) | 2023.09.21 |
|---|---|
| [백준] 12908번 : 텔레포트 (C++) (0) | 2023.09.20 |
| [백준] 2160번 : 그림 비교 (C++) (0) | 2023.09.20 |
| [백준] 13414번 : 오셀로 재배치 (C++) (0) | 2023.09.19 |
| [백준] 12015번 : 가장 긴 증가하는 부분 수열 2 (C++) (0) | 2023.09.18 |
