숫자 타자 대회

[geonnho0]

문제 링크

[geonnho0]

dp 배열의 정의는 다음과 같아요.

• dp[index][L][R] : index번째 숫자를 기준으로, 왼쪽/오른쪽 손가락이 L/R를 누르고 있을 때의 최소 경로의 합

현재 누르려는 0번째 숫자가 num이라고 가정하면,

1. num != R 이라면, 1번째 숫자를 기준으로 왼쪽 손가락을 num을 누르게 할 경우의 최소 경로를 구해요. (dfs(index + 1, num, R) + cost[L][num])
2. num != L 이라면, 1번째 숫자를 기준으로 오른쪽 손가락을 num을 누르게 할 경우의 최소 경로를 구해요. (dfs(index + 1, L, num) + cost[num][R])

위 2개의 값 중, 작은 값이 dp[0][L][R]에 해당돼요. 만약 num = L = R 일 경우엔, 불가능한 상황이기 때문에 dp 의 값은 최대값으로 설정돼요.

코드

class Solution {

    int[][] cost = {
        { 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[][][] dp;
    String numbers;
    int N;

    public int solution(String numbers) {
        init(numbers);
        return dfs(0, 4, 6);
    }

    void init(String numbers) {
        this.numbers = numbers;
        N = numbers.length();
        dp = new int[N + 1][10][10];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j < 10; j++)
                Arrays.fill(dp[i][j], -1);
        }
    }

    int dfs(int index, int L, int R) {
        if (index == N)
            return 0;
        if (dp[index][L][R] != -1)
            return dp[index][L][R];

        int num = numbers.charAt(index) - '0';
        int res = Integer.MAX_VALUE;

        if (num != R)
            res = Math.min(dfs(index + 1, num, R) + cost[L][num], res);
        if (num != L)
            res = Math.min(dfs(index + 1, L, num) + cost[R][num], res);

        return dp[index][L][R] = res;
    }

}