숫자 타자 대회

문제 링크

숫자 타자 대회

분석

키패드는 $4 \times 3$ 배열입니다.

1 2 3
4 5 6
7 8 9
* 0 #

처음 왼손 엄지는 4, 오른손 엄지는 6에 위치해 있습니다.

손가락을 통해 numbers의 순서대로 각 숫자를 눌러야 합니다.
이때, 손가락의 이동에는 가중치가 있으며, 두 손가락이 동시에 같은 버튼에 있을 수 없습니다.

이렇게 numbers의 각 숫자를 누르면서 생기는 총 가중치의 최솟값을 찾아 반환해야합니다.

가중치는 다음과 같습니다.

  • 같은 자리일 경우 1
  • 인접한 상하좌우 이동일 경우 2
  • 인접한 대각선 이동일 경우 3
  • 인접하지 않은 숫자는 위의 인접한 이동을 통한 이동으로 가중치가 결정

풀이

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

// 숫자의 키패드 위치를 행과 열로 반환하는 함수
pair<int, int> getPos(int num)
{
    // 0은 키패드에서 3, 1에 위치합니다.
    if (num == 0)
    {
        return {3, 1};
    }
    
    // 3 x 3으로 배치되므로, 행(row), 열(col)은 다음 식으로 구할 수 있습니다.
    return {(num - 1) / 3, (num - 1) % 3};
}

int getCost(int from, int to)
{
    // 이미 같은 위치인 경우
    if (from == to)
    {
        return 1;
    }
    
    // form과 to의 좌표를 구해 저장합니다.
    auto [r1, c1] = getPos(from);
    auto [r2, c2] = getPos(to);
    
    // 행과 열의 차이에 대한 절대값을 저장합니다.
    int rowDiff = abs(r1 - r2);
    int colDiff = abs(c1 - c2);

    // 대각선 이동 횟수로 행과 열 차이 중 작은 값이 됩니다.
    int diagonalMoves = min(rowDiff, colDiff);

    // 직선 이동 횟수로 차이가 큰 값 중 대각선 이동 횟수를 뺀 값입니다.
    int straightMoves = max(rowDiff, colDiff) - diagonalMoves;
    
    // 각 이동 횟수에 가중치를 곱해줍니다.
    return 3 * diagonalMoves + 2 * straightMoves;
}

int dfs(const string& numbers, int index, int left, int right, vector<vector<vector<int>>>& dp)
{
    // 재귀 종료 조건으로서 모든 숫자를 다 누른 경우 비용이 0입니다.
    if (index == numbers.size())
    {
        return 0;
    }
    
    // 이미 계산한 상태인 경우 저장된 값 반환
    int& cachedDPValue = dp[index][left][right];
    
    if (cachedDPValue != INT_MAX)
    {
        return cachedDPValue;
    }
    
    // 현재 눌러야 할 숫자
    int num = numbers[index] - '0';
    
    // 왼손이 num 위치로 이동할 때 오른손과 겹치지 않는 경우
    if (num != right)
    {
        // 왼손에서 num 위치로 이동할 경우의 이동 비용
        int leftCost = getCost(left, num);

        // 다음 숫자를 누르기 위해 재귀 호출
        int resLeft = dfs(numbers, index + 1, num, right, dp);

        // 왼손이 현재 숫자를 눌렀을 때 재귀 결과가 유효한 경우
        if (resLeft != INT_MAX)
        {
            // 비용 최소값 갱신
            cachedDPValue = min(cachedDPValue, leftCost + resLeft);
        }
    }
    
    // 오른손이 num 위치로 이동할 때 왼손과 겹치지 않는 경우
    if (num != left)
    {
        // 오른손에서 num 위치로 이동할 경우의 이동 비용
        int rightCost = getCost(right, num);

        // 다음 숫자를 누르기 위해 재귀 호출
        int resRight = dfs(numbers, index + 1, left, num, dp);

        // 오른손이 현재 숫자를 눌렀을 때 재귀 결과가 유효한 경우
        if (resRight != INT_MAX)
        {
            // 비용 최소값 갱신
            cachedDPValue = min(cachedDPValue, rightCost + resRight);
        }
    }
    
    // 현재 상태에서 누적된 최소 비용 반환
    return cachedDPValue;
}

int solution(string numbers) {
    // dp 배열을 초기화 합니다.
    // dp[index][left][right]는 index번째 숫자를 누를 때 왼손가락(left)과 오른손가락(right)의 위치에 따른 최소 비용을 저장
    vector<vector<vector<int>>> dp(numbers.size() + 1, vector<vector<int>>(11, vector<int>(11, INT_MAX)));
    
    return dfs(numbers, 0, 4, 6, dp);
}

성능 요약

시간 복잡도는 $O(n \times 100)$입니다.

  • DFS 함수의 호출 $O(n \times 10 \times 10)$

공간 복잡도는 $O(n \times 121)$입니다.

  • 각 손가락 위치마다의 최소 비용을 저장한 dp $O(n + 1 \times 11 \times 11)$
  • DFS 함수의 호출 스택 $O(n)$
  • $O(n + 1 \times 11 \times 11) + O(n)$
테스트 성능

테스트 1 〉 통과 (0.01ms, 3.68MB)
테스트 2 〉 통과 (0.01ms, 3.68MB)
테스트 3 〉 통과 (0.01ms, 4.19MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 3.62MB)
테스트 7 〉 통과 (0.02ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.21MB)
테스트 9 〉 통과 (0.02ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 3.63MB)
테스트 11 〉 통과 (0.03ms, 3.63MB)
테스트 12 〉 통과 (0.03ms, 4.16MB)
테스트 13 〉 통과 (0.03ms, 3.59MB)
테스트 14 〉 통과 (0.03ms, 4.21MB)
테스트 15 〉 통과 (0.03ms, 4.41MB)
테스트 16 〉 통과 (29.00ms, 25.8MB)
테스트 17 〉 통과 (48.69ms, 39.3MB)
테스트 18 〉 통과 (80.36ms, 56.8MB)
테스트 19 〉 통과 (129.68ms, 79.5MB)
테스트 20 〉 통과 (186.24ms, 108MB)

Programmers 카테고리 내 다른 글 보러가기

댓글남기기