[1일 1알고] 숫자 타자 대회

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

프로그래머스

 

오늘은 dp문제입니다.

 

문제를 읽어보면 풀이 방법이 dp임을 쉽게 알 수는 있습니다.

numbers의 길이가 최대 10만이고, 누를 수 있는 자판은 0~9이기 때문에

 

3차원 벡터 혹은 2차원 벡터 두개를 통해 dp를 구성할 수 있을 것입니다.

저는 간단하게 3차원 벡터를 사용했습니다.

---

int GetWeight(int cur, int target, vector<pair<int, int>>& number_vector)
{
    if (cur == target)
        return 1;
    int weight = 0;
    int dr = abs(number_vector[cur].first - number_vector[target].first);
    int dc = abs(number_vector[cur].second - number_vector[target].second);

    weight += 3 * min(dr, dc);
    weight += 2 * (abs(dr - dc));

    return weight;
}

int solution(string numbers) {
    int len = numbers.size();

    vector<pair<int, int>> number_vector = 
    {
        {3, 1}, {0, 0}, {0, 1}, {0, 2},
        {1, 0}, {1, 1}, {1, 2},
        {2, 0}, {2, 1}, {2, 2},
    };

    int INF = 1e9;
    vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(10, vector<int>(10, INF)));
    dp[0][4][6] = 0;
    for (int k = 1; k <= len; ++k)
    {
        for (int i = 0; i <= 9; ++i) // left hand
        {
            for (int j = 0; j <= 9; ++j)// right hand
            {
                if (dp[k-1][i][j] == INF)
                    continue;

                int target = numbers[k-1] - '0';

                if (i == target)
                {
                    dp[k][i][j] = min(dp[k][i][j], dp[k - 1][i][j] + 1);
                    continue;
                }

                if (j == target)
                {
                    dp[k][i][j] = min(dp[k][i][j], dp[k - 1][i][j] + 1);
                    continue;
                }
                dp[k][target][j] = min(dp[k][target][j], 
                    dp[k-1][i][j]  + GetWeight(i, target, number_vector));
                dp[k][i][target] = min(dp[k][i][target], 
                    dp[k-1][i][j] + GetWeight(j, target, number_vector));
            }
        }
    }

    int answer = INF;

    for (int i = 0; i <= 9; ++i)
    {
        for (int j = 0; j <= 9; ++j)
        {
            answer = min(answer, dp[len][i][j]);
        }
    }

    return answer;
}

자판에 대응하는 위치를 미리 구성하고(number_vector), 현재 위치와 목표 위치 사이에서 발생하는 cost를 반환하는 함수도 만들었습니다.

 

이를 활용하면 비교적 간단하게 dp문제를 해결할 수 있습니다.