문제 요약 및 풀이
주어지는 문자열을 접어서, 같은 문자열로만 이루어지는 문자열을 만들어내면 된다.
문제에서 주어지는 예시를 쭉 보다보면, 한가지 사항을 발견할 수 있다.
만들어내는 문자열의 각 문자의 원래 문자열에서의 위치는 서로 홀수만큼 차이가 난다. (사이에 있는 숫자 갯수를 말하는 것이 아닌, 위치의 차이다.)
따라서, 최대한 같은 문자를, 위치가 홀수만큼 차이가 나는 문자들을 선택하면 된다.
물론 하나하나 따져가면 시간초과가 뜰테니.. DP로 풀어나갔다.
풀이 코드
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
#include <bits/stdc++.h>
#define for1(s,n) for(int i = s; i < n; i++)
#define for1j(s,n) for(int j = s; j < n; j++)
using namespace std;
string s; // 입력받을 문자열
int d[1100], ans; // d: DP 배열, d[i] = i번째 문자를 사용했을 때, 만들 수 있는 최대 문자열 길이
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> s;
int n = s.length();
for1(0, n) d[i] = 1; // 어찌되었든, 문자열을 접지 않으면, 모든 문자가 1로 가능하다.
for1(1, n) {
for1j(0, i) {
if((i - j) % 2 && s[i] == s[j]) {
// 홀수 간격이고, 문자가 같은 경우
d[i] = max(d[i], d[j] + 1);
}
}
}
for1(0, n) {
// DP 배열에서 최대값을 뽑아낸다.
ans = max(d[i], ans);
}
cout << ans;
}