백준 23759 비슷한 문자열

문제설명

접근방식

길이가 K인 N개의 문자열을 받아서 처리하는 문제로 동일한 인덱스에 같은 문자가 있는 비슷한 문자열의 개수를 세어줘야 한다. 아이디어를 떠올리기 굉장히 어려운 문제였고 나 또한 같은 팀원분들의 풀이를 듣고 이해할 수 있었다. 아이디어 자체가 떠올리기도 어렵고 들어도 바로 직관적으로 이해하기는 쉬운 편은 아니지만 모든 DP 문제가 그러하듯이 핵심 아이디어만 생각해내면 풀리게 되니 핵심 아이디어만 정리해보도록 하자.

핵심 아이디어

dp[i][j] 
문자열에서 i번째 위치에서 j의 문자가 나왔을 때 
그 위치의 그 문자를 기준으로 구성할 수 있는 최대 인접 문자열의 수

a e -> 1 1
c d -> 1 1
a a -> 2 1 --> 2 2
z a -> 2 3 --> 3 3
c e -> 1 3

예제를 바탕으로 풀이를 정리해보면 각각의 i번째 문자열에서 j인덱스에서 a~z까지 모든 알파벳 문자의 현재 위치까지의 현재 인덱스에서 등장한 횟수를 저장하도록 한다. 이렇게 하면 일반적인 dp의 방식으로 이전까지의 계산결과를 바탕으로 현재의 계산결과를 구할 수 있게 된다. 이것이 현재 위치의 특정 인덱스의 특정 문자를 기준으로 얻어낼 수 있는 비슷한 문자열의 개수와 동일하다.

여기서 추가로 고려해야할 지점은 특정 문자로 이어져오던 비슷한 문자열이 특정 지점에서 다른 인덱스의 다른 문자를 통해서 계속해서 연결될 수 있다는 점이다.

a b c -> 1 1 1
a x x -> 2 1 1 -> 2 2 2
a y k -> 3 1 1 -> 3 3 3
b z k -> 1 1 4 -> 4 4 4

이런 방식으로 연결될 수 있기 때문에 한 문자열을 다 탐색하고 난 뒤에는 그 문자열에서 얻은 가장 큰 값으로 그 문자열에서의 특정 인덱스의 특정 문자의 dp값을 최대값으로 동일하게 맞춰주는 업데이트 작업을 해줘야 한다.

C++코드

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

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <int, int>;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  freopen("inp.txt", "r", stdin);

  int N, K;
  cin >> N >> K;

  vector<vector<int>> dp(K, vector<int>(26, 0));
  
  for(int i=0; i<N; i++){
    string temp;
    cin >> temp;

    // i번쨰 위치에 'a'+j 문자가 나오게 되면 그 위치의 문자를 기점으로
    // 지금까지 만들 수 있는 최장 인접 문자열의 수를 구함
    // 그리고 문자열을 읽으면서 그 중에서 최댓값을 구해놓음
    int max_val = -1;
    for(int i=0; i<K; i++){
      dp[i][temp[i]-'a']++;
      max_val = max(max_val, dp[i][temp[i]-'a']);
    }

    // 하나의 문자열에 속하므로 비록 이번이 자기를 중점으로 연결된 것을 아니더라도 
    // 다른 위치의 문자와 함께 같은 값을 가져야 함
    // 그래서 나중에 뒤에서 같은 위치의 같은 문자가 나와서 호출될 때
    // 자신을 포함한 다른 문자들을 통해서 얻어진 최장 인접 문자열의 수 알려줌
    for(int i=0; i<K; i++)
      dp[i][temp[i]-'a'] = max_val;
  }

  // ans check & output
  int ans = -1;
  for(int i=0; i<K; i++){
    for(int j=0; j<26; j++)
      ans = max(ans, dp[i][j]);
  }
  cout << N - ans;
}

/*
DP[i][j] 
문자열에서 i번째 위치에서 j의 문자가 나왔을 때 
그 위치의 그 문자를 기준으로 구성할 수 있는 최대 인접 문자열의 수
*/