[C++][프로그래머스] 숫자 타자 대회 🔥

프로그래머스

 

📄 문제

• 이동하지 않고 제자리에서 다시 누르는 것은 가중치가 1입니다.
• 상하좌우로 인접한 숫자로 이동하여 누르는 것은 가중치가 2입니다.
• 대각선으로 인접한 숫자로 이동하여 누르는 것은 가중치가 3입니다.
• 같지 않고 인접하지 않은 숫자를 누를 때는 위 규칙에 따라 가중치 합이 최소가 되는 경로를 따릅니다.

 

예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.
단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

숫자로 이루어진 문자열 numbers가 주어졌을 때 최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 하도록 solution 함수를 완성해주세요.

 

📝 풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<char, pair<int, int>> m;
int dp[100001][10][10];

int getWeight(int from, char c) {
    // from을 기준으로 c에 해당하는 x, y의 길이를 가져오기
    int x = abs(m[c].first - m[from + '0'].first) ;
    int y = abs(m[c].second - m[from + '0'].second);
    
    int weight = -1;
    if(!x && !y) // 만약 x, y가 from과 같은 위치라면 1 리턴
        return 1;
    else if(!x || !y) // 만약 x나 y중 하나가 0이라면, 직선 거리만 사용하기에 큰 값 * 2 리턴
        return max(x, y) * 2;
    else // 대각선이 포함된경우 직선거리 * 2 + 대각선거리 * 3 리턴
    {
        int minValue = min(x, y);
        x -= minValue;
        y -= minValue;
        return minValue * 3 + max(x, y) * 2;
    }
}

int func(string& numbers, int left = 4, int right = 6, int idx = 0) {
    // 끝까지 검사하였다면 리턴
    if(idx == numbers.size())
        return 0;

    // 두 손가락의 위치가 같으면 안되기에 매우 큰 수를 리턴하여 사용할 수 없도록 함
    if(left == right)
        return 99999999;
    
    // 이미 해당 값이 있다면, 중복 연산을 피하기 위하여 즉시 리턴
    if(dp[idx][left][right])
        return dp[idx][left][right];
    
    // 현재 left와 right의 위치에서 numbers[idx]까지의 가중치를 구하기
    int leftW1 = getWeight(left, numbers[idx]);
    int rightW1 = getWeight(right, numbers[idx]);
    
    // left와 right를 이용한 가중치를 각각 구하기
    int leftW2 = leftW1 + func(numbers, numbers[idx] - '0', right, idx + 1);
    int rightW2 = rightW1 + func(numbers, left, numbers[idx] - '0', idx + 1);

    // 각 가중치에서 최소값을 선택
    return dp[idx][left][right] = min(leftW2, rightW2);
}

int solution(string numbers) {
    // 숫자 글자에 해당하는 위치를 map에 저장
    char c = '1';
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j)
            m[c++] = {i, j};
    m['0'] = {3, 1};
  
    // 정답 구하기
    return func(numbers);
}

• numbers의 길이가 100,000이기때문에 n^2로 해결할 수 없는 문제입니다.
• 탐욕법 해결법으로, 두 손가락의 현재 위치에서 가중치가 낮은 손가락을 사용하였을때에도 뒤에있는 값들을 고려해야하기에 이 방법으로도 해결할 수 없습니다.
• Top-Down 방식의 DP를 해결하여 문제를 해결할 수 있었습니다.
  
  • 현재 상태에서 왼손, 오른손을 사용할 때의 모든 경우의 수를 고려해야합니다.
  • 2 + 4 + 8 + 16 + 32.... 와 같이 계산을 해야 문제를 해결할 수 있지만, DP를 이용하여 중복된 계산을 회피할 수 있습니다.
• 왼손, 오른손을 모두 사용한다고 가정하였을 때, 누적된 가중치의 최소값을 찾아낼 수 있습니다.