[Algorithm] Programmers :: 숫자 타자 대회

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

프로그래머스

int dp[100001][10][10];
string targetNumbers;
 
int cost[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 DFS(int index, int left, int right)
{
    if (index == targetNumbers.size()) return 0;
    if (dp[index][left][right] != -1) return dp[index][left][right];
 
    int result = 0x3f3f3f3f;
    int targetNum = targetNumbers[index] - '0';
 
    if (targetNum != right) // 이동해야할 버튼에 오른손이 안올라가져 있다면
    {
        // 왼손이동
        result = min(result, DFS(index + 1, targetNum, right) + cost[left][targetNum]);
    }
 
    if (targetNum != left) // 이동해야할 버튼에 왼손이 안올라가져 있다면
    {
        // 오른손이동
        result = min(result, DFS(index + 1, left, targetNum) + cost[right][targetNum]);
    }
 
    return dp[index][left][right] = result;
}
 
int solution(string numbers) 
{
    targetNumbers = numbers;
    memset(dp, -1, sizeof(dp));
 
    return DFS(0,4,6);
}

 

그리디하게 풀릴줄알고 처음에는 그리디한 코드를 작성했었다. 

거진 맞긴했는데, 일부 케이스는 아예 틀리고 시간초과도 나왔었다.

가만히 생각해보니, 현재 위치에서 타겟위치까지의 가중치값을 비교해서 왼손을 옮길지 오른손을 옮길지 결정했었는데 값이 같을 경우 그냥 둘 다 탐색하게 했었다. 그러니 당연히 시간초과가 나올 수 밖에 없다.

 

틀린케이스에 대해서는 그냥 그리디한 접근자체가 잘못됐다는 거다. 무조건 가까운손으로 옮기는게 아니라, 일단 먼거를 먼저 옮기더라도 그게 정답이 될 수 있는 루트인 경우가 존재한다는 것이다.

 

그래서 dp풀이를 참고했고, dp의 각 요소는 다음과같다.

dp[index][L][R] == 타겟숫자의 index번째에서 왼손은 L번, 오른손은 R번에 있을때, 타겟숫자를 완성하기위한 최소가중치값.

 

각 호출에서 왼쪽,오른쪽 둘 다 비교해서 최솟값을 넣기때문에 '확실하게' dp값에는 최솟값이 들어가있다는게 보장되어진다. 그렇기 때문에 다른루트에서 접근했을 때 그대로 그 값을 리턴해주면 된다.

이동해야할 버튼에 이미 다른 손가락이 있다면 그 손가락으로 눌러야한다..라는게 조건이니 적절한 조건문을 거는것을 잊으면 안된다.