문제 이해 단계
https://www.acmicpc.net/problem/21941
소문자 문장 S가 주어지고, 문자열 리스트들이 주어진다.
각 문자열 리스트들은 각자 점수를 가지고 있다.
문장 S에서 모든 문자들을 지워야 하는데
아래 2가지 연산만 할 수 있다.
1. 문자열 리스트에 존재한다면 해당 부분을 지우고, 그 문자열만큼의 점수를 얻는다.
2. 문자 하나를 지우고 1점을 얻는다.
해당 연산을 통해 모든 문자를 지울 때, 얻을 수 있는 최댓값을 구하는 문제
문제 접근 단계
범위 파악
문제 조건부터 살펴보자.
문장 S는 최대 1000개까지, 문자열 리스트는 100개,
그리고 점수는 개당 10,000점까지 가능하다.
만약 문장의 길이가 1000이고,
문자열이 하나로 구성된, 개당 10,000점짜리가 100개라면
10^3 * 10^4 * 10^2 = 10^9 이므로 INT 자료형이 아슬아슬하다.
그래서 안전하게 long long을 써주는 것이 나아 보인다.
그리디로 못 푸는 이유
처음에는 그리디를 생각했다.
구해야 하는 것이 최댓값이고, 문자열 리스트가 짧고,
점수가 높은 것을 먼저 구할수록 무조건 점수가 높게 나올 것 같았다.
그런데 예외케이스가 존재했다.
백준 질문게시판에 있는 어떤 분이 올린 반례인데
bab
2
bab 5
a 2
정답 : 5
같은 경우다.
이 경우에는 길이가 더 긴 bab을 먼저 써야 최댓값이 나온다.
그럼 최댓값을 기준으로 정렬하면 되냐? 그렇지도 않다.
이것도 반례가 존재한다.
abcd
2
abcd 4
ab 3
정답 : 5
해당 경우에는 값이 큰 abcd를, 먼저 쓰면 최댓값이 나오지 않는다.
수에 따라 답이 달라지기 때문에 그리디로 풀기에는 무리가 있다.
그래서 그리디 말고 다른 방식이 필요했다.
DP 식 접근
어떤 한 인덱스에 있다고 생각해 보자.
한 인덱스에서 할 수 있는 선택지는 뭐가 있을까?
당연히 3가지 중 하나일 것이다.
만약 범위를 문장에서 범위를 정했을 때,
1.
그 범위에 특정 문자열 리스트가 포함되어 있다면
그 문자열 리스트에 해당하는 문자들을 지우는 것
2. 그 인덱스의 문자 하나를 지우는 것
3. 아무것도 하지 않는 것(지우지 않는 것)
하지만 사실 3번은 불가능하다.
왜냐하면 결국엔 문자를 모두 다 지워야 하기 때문이다.
문자를 남겨둔다고 해서 이득이 되는 것이 없기 때문에, 사실상 선택지는 2개다.
여기서 1번 조건을 실행시켜 주기 위해선
인덱스를 기준으로 하는 범위를 정해줘야 한다.
어떤 인덱스가 끝에 오거나, 중간에 오면
그 범위로 확장해서 그 문자열 리스트가 추가된 건지 아닌지 모르기 때문에
범위를 깔끔하게 인덱스 i가 범위의 가장 앞을 나타내도록 한다.
즉, Arr [i] = (i번째 인덱스를 시작점 ~ 끝까지의 길이)를 가진 문장이다.
예를 들어 인덱스가 0 ~ N-1이고, i번째 인덱스라면
Arr [i] = i번째부터 시작하여 N-1까지의 범위를 가진 문장을 뜻한다.
이를 통해 해당 인덱스로 시작하는 문장이
문자열 리스트에 있는 문자열을 가지고 있다면 1번 연산을 실행해 준다.
물론 1번 연산을 실행하지 않고 2번 연산을 실행할 수도 있기 때문에
2번 연산을 실행하는 경우의 수도 해줘서 둘 중 더 큰 경우의 수를 저장한다.
그리고 문자열을 사용해 줬으므로 그만큼 i+(문자열 길이)로 문장의 길이를 줄여준다.
그림을 나타내면 아래와 같다.
이런 식으로 계속 재귀함수를 호출해 주면서 dp에 값을 저장해 준다.
자세한 것은 문제 구현단계에서 본다.
문제 구현 단계
// 문자열 리스트 별 점수 구조체
struct Info{
string word;
int score;
};
int d[1001]; // 범위에 따른 최댓값을 담아둠
vector<Info> v; // 문자열 리스트
string sentence; // 문장
// dp
long long dp(int x){
// 이미 저장된 값이 있다면 그 값이 이용
if(d[x] != -1) return d[x];
if(x >= sentence.length()) return 0; // 인덱스가 넘어가면 0 반환
long long result = 0;
// 문자열 리스트가 부분 문장에 있는지 검사
for(int i = 0; i < v.size(); i++){
if(v[i].word == sentence.substr(x,v[i].word.length())){
// 그 중 최댓값
result = max(result,dp(x+v[i].word.length())+v[i].score);
}
}
// 그냥 단어 하나 삭제한 경우
result = max(result,dp(x+1)+1);
return d[x] = result; // dp 배열에 저장
}핵심이 되는 dp 함수이다.
문자열 별 점수를 묶기 위해 구조체 Info를 저장했다.
그리고 범위에 대한 최댓값을 메모라이징 해둘 배열 d를 선언해 뒀다.
dp함수에는 매개변수로 시작 알파벳을 뜻하는 인덱스를 받는다.
그렇기 때문에 이 값이 문장의 범위를 넘어가면 0을 반환하도록 한다.
전체적인 동작은 부분 문장에서 문자열 리스트에 해당하는 단어가 있는지 확인하여,
최댓값을 찾는 과정을 반복하는 것이다. 그리고 그 값을 d배열에 저장한다.
핵심적인 함수의 설명은 여기까지이고,
나머지 전체 코드를 아래 올려두고 마치겠다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
// 문자열 리스트 별 점수 구조체
struct Info{
string word;
int score;
};
int d[1001]; // 범위에 따른 최댓값을 담아둠
vector<Info> v; // 문자열 리스트
string sentence; // 문장
// dp
long long dp(int x){
// 이미 저장된 값이 있다면 그 값이 이용
if(d[x] != -1) return d[x];
if(x >= sentence.length()) return 0; // 인덱스가 넘어가면 0 반환
long long result = 0;
// 문자열 리스트가 부분 문장에 있는지 검사
for(int i = 0; i < v.size(); i++){
if(v[i].word == sentence.substr(x,v[i].word.length())){
// 그 중 최댓값
result = max(result,dp(x+v[i].word.length())+v[i].score);
}
}
// 그냥 단어 하나 삭제한 경우
result = max(result,dp(x+1)+1);
return d[x] = result; // dp 배열에 저장
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int M;
cin >> sentence >> M;
fill(d,d+1001,-1);
for(int i = 0; i < M; i++){
string word;
int score;
cin >> word >> score;
if(word.length() >= score) continue;
v.push_back({word,score});
}
long long ans = 0;
for(int i = sentence.length()-1; i >= 0; i--){
ans = max(ans,dp(i));
}
cout << ans;
}
시행착오
처음에는 그리디로 풀었다.
반례가 있는 줄 모르고 정렬 기준을 여러 번 바꿔보면서 했다.
정답 범위가 계속 94% 올라가길래 한 끗 차이로 틀린 줄 알았는데,
알고 보니 그냥 그리디 자체가 안 되는 거였다..
이게 dp였다니.. 완전히 낚였다..
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me