[programmers] 숫자 타자 대회

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

memoization 기법을 활용한 dp.

 

---------------------------------------------------풀이----------------------------------------------------

 

크게 두 가지 함수로 이루어져 있다.

먼저, dp를 활용한 dfs() 함수.

dp[numbers길이][왼손누르는숫자0~9][오른손누르는숫자0~9]를 저장하며 이 값을 이용하는 방식의 dp 문제이다.

numbers의 현재 누르려는 인덱스 cur_idx의 숫자에 대해, 왼손과 오른손의 위치가 l과 r일 때, 그 분기에서의 최솟값들을 매번 저장해둔다.

이미 그 분기의 최솟값이 찾아져있으면 dp[][][]를 리턴하고, 없다면 찾는 과정을 반복한다.

만약 왼손의 위치나 오른손의 위치의 숫자가 numbers[cur_idx]와 일치하면, 그 숫자를 누르고 cost는 +1 한다.

 

다음으로는, 손의 위치가 from 숫자일 때, to 숫자를 누를 때의 최소 cost를 구하는 calc_time()함수.

다른 분들의 풀이에서는 이 값을 미리 계산해서 배열에 선언하는 방식으로 구현했던데,

나는 귀찮아서 그걸 하진 않았다.

양쪽 다 적용해 보긴 했는데 시간차이가 없는 것으로 봤을 때, 이 방식으로 구한다해도 문제될 게 없어보인다.

여기도 일종의 memoization을 활용한 것인데, 필요하면 계산해서 from_to[][] 배열에 구한 값을 저장하고, 다음에는 이 값을 사용한다.

from과 to의 숫자에 따라 행과 열을 구하고, 이 값을 비교해 cost를 구한다.

예를 들어 from의 행, 열 값보다 to의 행, 열 값이 각각 크면 오른쪽 아래로 가야 하므로 우하향 대각선(cost=3)을 고르는 방식이다.

이 방식으로 from과 to가 같아질때까지 반복해 최소 cost를 계산한다.

#include <string>
#include <vector>
#include <limits.h>

using namespace std;

int answer;
string numbers;
int from_to[10][10] = {0,};
// dp[numbers길이][왼손누르는숫자0~9][오른손누르는숫자0~9]
int dp[100'001][10][10] = {0, };

// from에서 to를 누를 때 최소 시간 리턴
int calc_time(int from, int to){
    // 이미 저장된 목표까지 가는 저장된 값이 존재하면 바로 리턴
    if(from_to[from][to] > 0){
        return from_to[from][to];
    }
    
    int min_time = 0;
    // from의 행렬 구하기
    int from_row = (from-1)/3;
    int from_col = (from-1)%3;
    if(from == 0){
        from_row = 3;
        from_col = 1;
    }
    // to의 행렬 구하기
    int to_row = (to-1)/3;
    int to_col = (to-1)%3;
    if(to == 0){
        to_row = 3;
        to_col = 1;
    }
    // from에서 to로 이동하기 전까지 반복
    while(from_row != to_row || from_col != to_col){
        // 대각선 오른쪽아래 이동
        if(from_row < to_row && from_col < to_col){
            from_row++; from_col++;
            min_time += 3;
        }
        // 대각선 오른쪽위 이동
        else if(from_row > to_row && from_col < to_col){
            from_row--; from_col++;
            min_time += 3;
        }
        // 대각선 왼쪽아래 이동
        else if(from_row < to_row && from_col > to_col){
            from_row++; from_col--;
            min_time += 3;
        }
        // 대각선 왼쪽위 이동
        else if(from_row > to_row && from_col > to_col){
            from_row--; from_col--;
            min_time += 3;
        }
        // 오른쪽 이동
        else if(from_row == to_row && from_col < to_col){
            from_col++;
            min_time += 2;
        }
        // 왼쪽 이동
        else if(from_row == to_row && from_col > to_col){
            from_col--;
            min_time += 2;
        }
        // 아래 이동
        else if(from_row < to_row && from_col == to_col){
            from_row++;
            min_time += 2;
        }
        // 위 이동
        else if(from_row > to_row && from_col == to_col){
            from_row--;
            min_time += 2;
        }
    }
    from_to[from][to] = from_to[to][from] = min_time;
    return min_time;
}

// 왼손 위치, 오른손 위치, 현재 numbers의 인덱스
int dfs(int l, int r, int cur_idx){
    // cur_idx가 numbers를 넘어가면 종료
    if(cur_idx >= numbers.length()){
        return 0;
    }
    
    // 현재 계산하려는 분기가 이미 존재하면 그 값을 리턴
    if(dp[cur_idx][l][r] > 0){
        return dp[cur_idx][l][r];
    }
    
    // numbers[cur_idx]를 누를 차례임.
    int ans = INT_MAX;
    int cur_num = numbers[cur_idx] - '0';
    // l이나 r이 numbers[cur_idx]에 있는 경우
    if(l == cur_num || r == cur_num){
        ans = dfs(l, r, cur_idx+1) + 1;
        return ans;
    }
    // l로 누를 경우
    ans = min(ans, dfs(cur_num, r, cur_idx+1) + calc_time(l,cur_num));
    // r로 누를 경우
    ans = min(ans, dfs(l, cur_num, cur_idx+1) + calc_time(r,cur_num));
    
    // 구한 이 분기의 최솟값을 dp에 저장
    dp[cur_idx][l][r] = ans;
    return ans;
}

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

 

---------------------------------------------------후기----------------------------------------------------

 

특정 숫자에서 특정 숫자로 가는 최소 시간을 매번 찾으며 from_to[][] 배열에 저장해두었다.

그리고 왼쪽 손가락과 오른쪽 손가락의 위치에 대해 매번 바꿔가며 모든 경우의 수를 찾는 dfs 방식을 사용했더니,

20개의 테스트케이스 중 아래 5개 케이스에서 시간초과가 발생하였다.

사실 당연하다. numbers의 length가 100'000이니까...

어렵...

그래서 검색해 힌트를 얻은게 dp를 사용한다는 것!

dp는 점화식이라고만 생각했는데, 이건 그런 방식이 아니라, 이미 계산한 부분들을 저장해뒀다가 다시 사용할 수 있는 방식의 dp였다.

numbers의 k번째 인덱스일때 l과 r값에서 앞으로 선택해 나갈 때의 최솟값을 구했으면, 그 값을 저장해두고

또 이 분기에 도달했을 때는 저장된 값을 사용하는 방식!

기억해두는게 좋을 것 같다.

 

+ 이렇게 바꿨는데도 계속 시간초과가 나서 뭐가 문제인가 했더니...string numbers를 parameter로 넣어줘서 그런거였다....

앞으로는 parameter로 넘기는 부분을 최소화하고 전부 전역변수로 빼는게 효율적일 것 같다!!!