C++로 두 손가락으로 단어 입력하기: 최소 이동 거리 구하기 (동적 계획법 풀이)

문제 개요

다음과 같은 키보드 배치가 있다고 가정해 보겠습니다.

각 알파벳 대문자는 키보드 위의 특정 좌표에 위치합니다. 예를 들어 문자 A는 (0,0), B는 (0,1), P는 (2,3), Z는 (4,1)에 해당합니다. 이때 하나의 단어가 주어지면, 두 손가락만 사용하여 이 단어를 입력할 때 드는 최소 총 이동 거리를 구해야 합니다.

두 좌표 (x1, y1)과 (x2, y2) 사이의 거리는 |x1 − x2| + |y1 − y2|로 정의되는 맨해튼 거리입니다. 또한 각 손가락은 키보드 위의 어떤 위치에서든 자유롭게 시작할 수 있으며, 손가락이 처음 키를 누를 때는 이동 비용이 발생하지 않습니다.

예시

입력이 "HAPPY"라면 출력은 6입니다. 최적의 입력 방법은 다음과 같습니다.

• 첫 번째 손가락으로 H 입력 → 비용 0
• 첫 번째 손가락으로 A 입력 → H에서 A까지의 거리 2
• 두 번째 손가락으로 P 입력 → 비용 0
• 두 번째 손가락으로 P 입력 → 같은 위치이므로 비용 0
• 첫 번째 손가락으로 Y 입력 → A에서 Y까지의 거리 4

따라서 총 이동 거리는 0 + 2 + 0 + 0 + 4 = 6이 됩니다.

접근 방법: 메모이제이션 기반 동적 계획법

각 글자를 두 손가락 중 어느 쪽으로 누를지 선택해야 하므로, 모든 경우를 단순 탐색하면 지수 시간이 걸립니다. 그러나 두 손가락의 현재 위치와 현재까지 입력한 글자 수가 같은 상태라면 이후의 최소 비용도 항상 동일합니다. 따라서 메모이제이션을 적용해 한 번 계산한 상태의 결과를 재사용하면 효율적으로 해결할 수 있습니다.

풀이 과정은 다음과 같습니다.

• memo 맵 정의: 이미 계산한 상태의 최소 비용을 저장합니다.
• getHash() 함수: 두 손가락의 좌표와 현재 인덱스를 하나의 정수 상태 값으로 인코딩합니다.
• getXY() 함수: 문자 c에 대해 c − 'A'를 6으로 나눈 몫은 행, 나머지는 열로 하여 좌표를 구합니다. (한 줄에 6개의 키가 배치되어 있기 때문입니다.)
• getDist() 함수: 두 지점 사이의 맨해튼 거리를 반환하며, 손가락이 아직 어느 키에도 놓이지 않은 초기 상태(-1, -1)라면 0을 반환합니다.
• solve() 함수: 현재 글자를 첫 번째 손가락으로 누르는 경우와 두 번째 손가락으로 누르는 경우를 각각 재귀적으로 계산한 뒤, 더 작은 값을 선택합니다.

메인 함수에서는 solve(-1, -1, -1, -1, word, 0)을 호출하여 두 손가락 모두 초기 상태에서 탐색을 시작합니다. 상태 공간의 크기는 손가락 위치 조합(최대 26 × 26)과 글자 인덱스 N의 곱, 즉 O(N × 26²) 수준이므로 완전 탐색보다 훨씬 빠릅니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map<int, int> memo;
   int getHash(int a, int b, int c, int d, int e){
      int temp = 0;
      while (a) {
         temp = temp * 10 + a % 10;
         a /= 10;
      }
      while (b) {
         temp = temp * 10 + b % 10;
         b /= 10;
      }
      while (c) {
         temp = temp * 10 + c % 10;
         c /= 10;
      }
      while (d) {
         temp = temp * 10 + d % 10;
         d /= 10;
      }
      while (e) {
         temp = temp * 10 + e % 10;
         e /= 10;
      }
      return temp;
   }
   pair<int, int> getXY(char c){
      pair<int, int> ret;
      int a = c - 'A';
      ret.second = a % 6;
      ret.first = a / 6;
      return ret;
   }
   int getDist(int a, int b, int c, int d){
      if (a == -1 && b == -1)
         return 0;
      return abs(b - d) + abs(a - c);
   }
   int solve(int x1, int y1, int x2, int y2, string word, int idx){
      if (idx == word.size())
         return 0;
      int state = getHash(x1 + 2, y1 + 2, x2 + 2, y2 + 2, idx + 2);
      if (memo.find(state) != memo.end())
         return memo[state];
      pair<int, int> temp = getXY(word[idx]);
      int ans = 0;
      int A = getDist(x1, y1, temp.first, temp.second) +
      solve(temp.first, temp.second, x2, y2, word, idx + 1);
      int B = getDist(x2, y2, temp.first, temp.second) +
      solve(x1, y1, temp.first, temp.second, word, idx + 1);
      ans = min(A, B);
      return memo[state] = ans;
   }
   int minimumDistance(string word){
      memo.clear();
      return solve(-1, -1, -1, -1, word, 0);
   }
};
main(){
   Solution ob;
   cout << (ob.minimumDistance("HELLO"));
}

입력

"HELLO"

출력

4

이처럼 상태 해싱과 메모이제이션을 결합한 동적 계획법을 활용하면, 두 손가락의 모든 위치 조합을 효율적으로 관리하면서 단어 입력에 필요한 최소 이동 거리를 빠르게 계산할 수 있습니다.