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

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

처음 이 문제를 봤을 때, 단순히 그리디로 풀 수 있나? 고민을 했다.

하지만 어떤 손가락을 움직일지 선택을 하기 위해서는 뒤에 오는 숫자들에 규칙같은게 있어야 하는데,  없기 때문에 그리디로 풀면 안된다는 결론이 나왔다.

 

그래서 생각한 방법은 탐색이었는데, 탐색도 그냥 하기에는 너무 많기 때문에 DP로 문제를 해결했다.

손가락 위치를 기준으로 특정 숫자를 입력할 때, 내 손가락의 위치를 기록한 vector가 있다면, 최악의 경우 100,000*10*10으로 문제가 해결되기 때문이다.

 

그리고 특정 번호에서 다른 번호로 이동해서 누르는 경우의 가중치를 쉽게 계산하기 위해 계산을 도와줄 2차원 vector를 만들었다.

 

가중치를 쉽게 구하기 위해서 아래 그림과 같이 좌표를 기준으로 대각선으로 얼마나 떨어져있고, 상하좌우로는 얼마나 이동해야 하는지를 계산했다.

 

이후에는 number의 크기만큼의 길이와 왼손과 오른손의 좌표의 크기를 가진 3차원 vector에 왼손가락과 오른손가락의 위치에 따라 입력된 number에 따른 가중치의 최소값을 저장했다.

위 그림과 같이 3차원 vector에는 이전 number를 누른 경우에 왼손가락과 오른손가락의 위치에 따른 가중치의 최솟값을 저장하고 있다.

 

그러면 다음 number를 누르는 경우는 이전 최솟값들을 이용해 현재 number를 누를 경우에 왼손가락과 오른손가락의 위치에 따른 가중치의 최솟값을 빠르게 계산할 수 있다.

 

이후 최종적으로 모든 숫자를 눌렀을 때, 왼손가락과 오른손가락이 올 수 있는 위치들을 전부 탐색해 이 중 최솟값을 구하면 이게 가중치의 최솟값이다.

 

 

​

[아이디어 정리]

1. 계산을 편하게 하기 위해 특정 숫자에서 특정 숫자로 옮기는데 필요한 가중치를 미리 계산한다.
2. 3차원 vector를 이용해 특정 숫자를 누른 후 왼손가락과 오른손가락의 위치에 따른 가중치의 최솟값을 저장한다.
3. 이전 경우에서 구한 최솟값을 이용해 현재 특정 번호를 누를 경우에 손가락의 위치에 따라 가중치의 최솟값을 계산한다.
4. 모든 숫자를 다 눌렀을 경우 손가락의 위치들을 전부 탐색하고 그 중 최솟값을 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

int solution(string numbers) {
    int answer = 0;
    vector<vector<int>>Calc(10,vector<int>(10,0)); //이동을 쉽게 계산하기 위해 미리 계산
    for (int i=0; i<10; i++)
    {
        int numI=i;
        if (numI==0)
        {
            numI=10;
        }
        else
        {
            numI-=1;
        }
        int numIx=numI%3,numIy=numI/3;        
        for (int j=i; j<10; j++)
        {
            int numJ=j;
            if (numJ==0)
            {
                numJ=10;
            }
            else
            {
                numJ-=1;
            }
            int numJx=numJ%3,numJy=numJ/3;     
            int dy=abs(numIy-numJy),dx=abs(numIx-numJx);
            if (dy==0&&dx==0)
            {
                Calc[i][j]=1;
            }
            else
            {
                int V=0;
                while (dy>0||dx>0)
                {
                    if (dy>0&&dx>0)
                    {
                        dy--;
                        dx--;
                        V+=3;
                    }
                    else if (dy>0)
                    {
                        dy--;
                        V+=2;
                    }
                    else if (dx>0)
                    {
                        dx--;
                        V+=2;
                    }
                }
                Calc[i][j]=Calc[j][i]=V;
            }
        }
    }
    // 실제로 DP를 이용해 최소 값 계산
    vector<vector<vector<int>>> DP(numbers.length(),vector<vector<int>>(10,vector<int>(10,7000000))); //왼손 오른손 순서
    int a=numbers[0]-'0';
    DP[0][4][a]=Calc[6][a];
    DP[0][a][6]=Calc[4][a];
    for (int i=1; i<numbers.length(); i++)
    {
        a=numbers[i]-'0';
        for (int le=0; le<10; le++)
        {
            for (int ri=0; ri<10; ri++)
            {
                if (DP[i-1][le][ri]<7000000)
                {
                    if (le==a)
                    {
                        DP[i][a][ri]=min(DP[i][a][ri],DP[i-1][le][ri]+Calc[le][a]);
                    }
                    else if(ri==a)
                    {
                        DP[i][le][a]=min(DP[i][le][a],DP[i-1][le][ri]+Calc[ri][a]);
                    }
                    else
                    {
                        DP[i][a][ri]=min(DP[i][a][ri],DP[i-1][le][ri]+Calc[le][a]); //le를 a로
                        DP[i][le][a]=min(DP[i][le][a],DP[i-1][le][ri]+Calc[ri][a]); //ri를 a로                   
                    }
                }
            }
        }
    }
    int minV=70000000;
    for (int i=0; i<10; i++)
    {
        for (int j=0; j<10; j++)
        {
            minV=min(minV,DP[numbers.length()-1][i][j]);
        }        
    }
    return minV;
}

 

---

 

다른 사람들의 풀이를 봤더니, 특정 숫자에서 특정 숫자로 이동하는데 필요한 가중치를 손으로 그냥 바로 적은게 보였다...

나도 그냥 그렇게 할 껄 그랬나

 

프로그래머스