숫자 타자 습

import java.util.*;

class Solution {
    static 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 }
    };
    static String num="";
    static int N;
    static int answer;
    public int solution(String numbers) {
        answer = Integer.MAX_VALUE;
        num=numbers;
        N=numbers.length();
        
        dfs(0,4,6,0);
        
        return answer;
    }
    
    static void dfs(int depth, int L, int R, int sum){
        if(depth==N){
            answer = Math.min(answer,sum);
            return;
        }
        
        int targetNumber = num.charAt(depth)-'0';
        if(R!=targetNumber)dfs(depth+1,targetNumber,R,sum+cost[L][targetNumber] );
        if(L!=targetNumber)dfs(depth+1,L,targetNumber,sum+cost[targetNumber][R] );
        
    }
    
}

첨엔 이 방식으로 풀었음. 

근데 이렇게 되면 완탐을 하고, 시간이 터짐