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

https://school.programmers.co.kr/learn/courses/30/lessons/136797

프로그래머스

프로그래머스 - 숫자 타자 대회

문제 유형 : 다이나믹 프로그래밍, 재귀, dfs

문제 난이도 : Level 3

 

문제 설명

위와 같은 모양으로 배열된 숫자 자판이 있습니다. 숫자 타자 대회는 이 동일한 자판을 사용하여 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회입니다.

대회에 참가하려는 민희는 두 엄지 손가락을 이용하여 타이핑을 합니다. 민희는 항상 왼손 엄지를 4 위에, 오른손 엄지를 6 위에 두고 타이핑을 시작합니다. 엄지 손가락을 움직여 다음 숫자를 누르는 데에는 일정 시간이 듭니다. 민희는 어떤 두 숫자를 연속으로 입력하는 시간 비용을 몇몇 가중치로 분류하였습니다.

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

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

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

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
  • numbers는 아라비아 숫자로만 이루어진 문자열입니다.

 

풀이

dp[인덱스][왼쪽위치][오른쪽위치]로 최소비용을 저장하게 합니다.

 

만약 인덱스가 끝에 왔다면, 0을 반환합니다.

만약 같은 인덱스와 위치에서 값을 구한 적이 있다면, dp에서 꺼내서 반환합니다.

 

만약 다음으로 누를 버튼이 이미 왼쪽 또는 오른쪽에 있다면, 인덱스만+1한 경우의 수에 1을 더한 값을 반환합니다.

 

아니라면, 왼쪽과 오른쪽을 누른 경우의 수 중에서 더 비용이 덜 드는 것을 선택합니다.

 

이 과정을 재귀적으로 반복하면 됩니다.

 

코드

C++

#include <bits/stdc++.h>
using namespace std;

const int weight[10][10] = {
    { 1, 7, 6, 7, 5, 4, 5, 3, 2, 3 },
    { 7, 1, 2, 4, 2, 3, 5, 4, 5, 6 },
    { 6, 2, 1, 2, 3, 2, 3, 5, 4, 5 },
    { 7, 4, 2, 1, 5, 3, 2, 6, 5, 4 },
    { 5, 2, 3, 5, 1, 2, 4, 2, 3, 5 },
    { 4, 3, 2, 3, 2, 1, 2, 3, 2, 3 },
    { 5, 5, 3, 2, 4, 2, 1, 5, 3, 2 },
    { 3, 4, 5, 6, 2, 3, 5, 1, 2, 4 },
    { 2, 5, 4, 5, 3, 2, 3, 2, 1, 2 },
    { 3, 6, 5, 4, 5, 3, 2, 4, 2, 1 }
};

int dp[100001][10][10];

string nums;

int solve(int idx, int left, int right) {
    if (idx == nums.length()) return 0;
    int& result = dp[idx][left][right];
    if (result != -1) {
        return result;
    }
    
    int target = nums[idx] - '0';

    //손가락 움직일필요 없음
    if (left == target || right == target) {
        return result = 1 + solve(idx + 1, left, right);
    }

    //손가락 움직여보자..
    return result = min(solve(idx + 1, target, right) + weight[left][target]
        , solve(idx + 1, left, target) + weight[right][target]);
}

int solution(string numbers) {
    memset(dp, -1, sizeof(dp));
    nums = numbers;

    return solve(0, 4, 6);
}