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

해설

질문하기 게시판에 있는 가중치 맵을 사용했다.

i에서 j로 이동할 때의 최소 가중치를 비교한것. 예시로 0번에서 1번으로 이동하는 [0,1] 을 보면 가중치가 7이다. 가중치 맵을 이용하면 코스트를 빠르게 구할 수 있다!

가중치 맵의 링크는 여기

https://school.programmers.co.kr/questions/39574

프로그래머스

 

 

DP방식으로 푼 다른 분들의 코드를 보고 풀었다. 처음엔 그리디로 접근하고 있었는데 그리디로 문제를 해결하면 안되는 상황들이 나온다. 아래는 질문하기의 어떤 사람 분의 잘못된 접근법에서 가져온 글.

그리디 접근법이 틀렸다는 예시

따라서 DP로 풀어야 한다.

 

현재 인덱스, 현재 왼손의 위치, 현재 오른손의 위치

이렇게 3개의 인자를 받는 함수를 만들어서 왼손이 움직였을 경우, 오른손이 움직였을 경우의 코스트를 계산한 뒤 비교해준다. 

 

알고리즘 자체는 그렇게 복잡하지 않다. 그런데 어떤 방식으로 풀어야하는지 접근하는게 조금 어려웠다.. 이런 문제를 다음에 만났을 때 풀어낼 수 있도록 공부하는 시간을 가졌다고 생각하려고 한다 ㅠ

---

문제 설명

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

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

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

예를 들어 1 위에 있던 손가락을 0 으로 이동하여 누르는 것은 2 + 2 + 3 = 7 만큼의 가중치를 갖습니다.

단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

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

---

제한사항

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

---

코드

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 1e5 + 1;
const int NUMBER_MAX = 10;

const int WeightMap[NUMBER_MAX][NUMBER_MAX] = {
    { 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 }
};

// numbers.index, 왼손가락, 오른손가락이 위치한 숫자
int cache[MAX][NUMBER_MAX][NUMBER_MAX];

string copyNumbers;

int func(int idx, int left, int right)
{
    // copyNumbers의 길이보다 보다 idx의 크기가 클 때
    if (idx == copyNumbers.length())
        return 0;

    int& result = cache[idx][left][right];

    // 이미 계산된 결과가 존재할 때 
    if (result != -1)
        return result;

    int cur = copyNumbers[idx] - '0';

    // 엄지나 오른손의 위치가 이미 그 자리에 있었을 때
    // 가중치를 1 더해주고 다음으로 넘어간다
    if (left == cur || right == cur)
        return result = 1 + func(idx + 1, left, right);

    // 왼손이 움직인 코스트
    int a = func(idx + 1, cur, right);
    int b = WeightMap[left][cur];

    // 오른손이 움직인 코스트
    int c = func(idx + 1, left, cur);
    int d = WeightMap[right][cur];

    return result = min(a + b, c + d);
}

int solution(string numbers) {
    memset(cache, -1, sizeof(cache));
    copyNumbers = numbers;

    return func(0, 4, 6);
}