[프로그래머스] Level 3. 숫자 타자 대회

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

프로그래머스

 

이 문제는 DP (동적 계획법) 을 사용해야 하는 문제이다. 첫번째 문자열부터 시작해서, 결과값을 저장한다. 다음 문자열을 검사할 때, 이전 기록을 가져와 최적의답을 찾는다.

 

해결방법

• 3차원 배열 m을 선언한다. m[1][2][3] 은 첫번째 문자열까지 눌렀고, 왼손이 2, 오른손이 3일때의 최솟값이다. 
• 우리의 목표는 m[문자열사이즈] 에서의 최솟값을 찾는 것이다.
• m[0][4][6] = 0 을 넣는다. 이는, 시작할때 왼손에 4, 오른손에 6이 들어있음을 의미한다. 
• 이제 문자열을 하나씩 돌면서 왼손 0~9, 오른손0~9를 모두 검사한다.
  • 만약 왼손과 오른손이 같거나, 값이 매겨지지 않았다면(INT_MAX. 경로가 없다는 의미) 패스한다.
  • 왼손이 간다고 가정했을때, 도달할 배열은 m[현재문자열+1][next숫자][오른손] 이다.
  • 이미 저장되어있는 경우, 최솟값 vs  m[현재문자열][현재왼손][현재오른손] + 왼손을 next숫자로 이동시키는 cost 두개를 비교하여 최솟값을 골라  m[현재문자열+1][next숫자][오른손] 에 갱신한다. 왼손을 옮겼을 경우이다.
  • 오른손도 마찬가지로 계산해준다.
  • 모든문자열까지 반복한다.
• 비용을 찾는 것은 직접 찾는것도 있고, costs를 넣는 방법도 있으나 나의 경우 costs 배열을 만들어서 사용했다. 숫자가 작기도 하고, 매번 찾는것보다는 직접 조회하는 것이 더 빠를것 같았다. 

#include <string>
#include <vector>
#include <iostream>
#include <climits>

using namespace std;

vector<vector<int>> costs = {{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 solution(string numbers) {
    vector<vector<vector<int>>> m(numbers.size()+1,vector<vector<int>>(10,vector<int>(10,INT_MAX))); //i : 문자열 수 , j : 왼손 k : 오른손
    m[0][4][6] = 0;
    for(int i = 1; i<=numbers.size(); i++){
        int n = numbers[i-1]-'0';
        for(int j =0; j<10; j++){
            for(int k= 0; k<10; k++){
                if(j == k || m[i-1][j][k] == INT_MAX) continue; //두손이 겹치거나, 경우의수에 없을 경우
                m[i][n][k] = min(m[i][n][k],m[i-1][j][k]+costs[j][n]); //왼손
                m[i][j][n] = min(m[i][j][n], m[i-1][j][k] + costs[k][n]); //오른손
            }    
        }
    }
   
    
    int answer = INT_MAX;
    for(int i = 0 ; i<10; i++){
        for(int j= 0; j<10; j++){
            int val = m[numbers.size()][i][j];
            if(val < answer) answer = val;
        }
        
    }
    return answer;
}

 

 

마무리하며

dp는 나에게 정말 어려운 알고리즘이다.. 이것도 정답을 보고 깨우친건데, 처음 코드를 봤을땐 이해가 안될정도였다. 비슷한 dp문제를 많이 풀어보고 익혀야 할 것 같다.