숫자 타자 대회

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

구현 아이디어 ... 구현 ...

실패

매번 다음 단계의 선택은 이전 단계에서 l을 썼던 때와 r을 썼던 때 중에서 더 적은 값을 선택하면 된다.라고 생각은 했는데 어떻게 구현할지 감이 안 왔다...

---

풀이(2023년 11월 29일)

1. 0~9의 가중치 배열을 구한다.
2. Dp 배열은 Dp[Index][Left][Right]이다.
3. 만약 Str이 "12"라면,
   (왼손이 1, 오른손이 6일 때 2를 누르는 가중치) + (현재 4인 왼손이 1을 누르는 가중치),
   (왼손이 4, 오른손이 1일 때 2를 누르는 가중치) + (현재 6인 오른손이 1을 누르는 가중치) 중 적은값이 답이다.

#include <string>
#include <vector>

using namespace std;

int Weight[10][10] = {
    {1, 7, 6, 7, 5, 4, 5, 3, 2, 3}, // 0~
    {7, 1, 2, 4, 2, 3, 5, 4, 5, 6}, // 1~
    {6, 2, 1, 2, 3, 2, 3, 5, 4, 5}, // 2~
    {7, 4, 2, 1, 5, 3, 2, 6, 5, 4}, // 3~
    {5, 2, 3, 5, 1, 2, 4, 2, 3, 5}, // 4~
    {4, 3, 2, 3, 2, 1, 2, 3, 2, 3}, // 5~
    {5, 5, 3, 2, 4, 2, 1, 5, 3, 2}, // 6~
    {3, 4, 5, 6, 2, 3, 5, 1, 2, 4}, // 7~
    {2, 5, 4, 5, 3, 2, 3, 2, 1, 2}, // 8~
    {3, 6, 5, 4, 5, 3, 2, 4, 2, 1}, // 9~
};
string Str;
int Dp[100001][10][10];

int DFS(int Index, int Left, int Right)
{
    if(Index == Str.size()) return 0;
    if(Dp[Index][Left][Right] > 0) return Dp[Index][Left][Right];   // 구했던 값 재활용.
    
    int CurNumber = Str[Index] - '0';
    int Minimum = 2147000000;
    
    if(CurNumber != Right)  // 왼손 입력.
    {
        Minimum = (DFS(Index + 1, CurNumber, Right) + Weight[Left][CurNumber]);
    }
    if(CurNumber != Left)   // 오른손 입력.
    {
        Minimum = min(Minimum,
                     DFS(Index + 1, Left, CurNumber) + Weight[Right][CurNumber]);
    }
    
    return Dp[Index][Left][Right] = Minimum;
}

int solution(string numbers) {
    int answer = 0;
    Str = numbers;
    answer = DFS(0, 4, 6);
    return answer;
}