[pro] 프로그래머스 level3 136797 숫자 타자 대회 (Java) - dfs, dp

[문제]

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

프로그래머스

 

[풀이]

dp를 이용해 메모이제이션 하지 않는다면 테스트케이스 후반부에 시간초과가 발생한다.

 

1. 먼저 0~9까지의 숫자에 대한 가중치 배열을 초기화한다. cost[i][j]에는 키패드의 숫자 i에서 j로 손가락을 움직일 경우의 가중치 값이 저장되어 있다. 같지 않고 인접하지 않는 숫자를 누를 경우, cost[i][j] = min*3 + (max-min)*2와 같이 표현할 수 있다. 

2. 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 하기 때문에 이에 대한 예외처리를 해주었다.

dp[idx][left][right]에 해당 인덱스에서 left, right 위치에 있을 때의 가중치 합을 저장해주고, 만약 dp[idx][left][right]가 -1이 아니라면 이미 계산되었던 값이므로 그대로 반환한다.(메모이제이션)

 

[코드]

 

import java.util.*;

class Solution {    
    int[][] cost;
    int[][][] dp;
    int len;
    String nums;
   
    public int solution(String numbers) {
        int answer = 0;
        //최소한의 시간으로 타이핑을 하는 경우의 가중치 합을 return 
        
        initCost();
        
        len = numbers.length();
        nums = numbers;
        dp = new int[len][10][10]; //idx, left, right
        
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < 10; j++)
                Arrays.fill(dp[i][j], -1);
        }
        
        return solve(0, 4, 6);
    
    }
    
    public int solve(int idx, int left, int right){
        if(idx==len){
            return 0; //문자열 끝까지 탐색한 경우
        }
        //이미 계산된 경우
        if(dp[idx][left][right]!=-1) return dp[idx][left][right];
        
        int num = nums.charAt(idx) - '0';
        int ans = Integer.MAX_VALUE;
        
        //왼쪽 손가락을 움직이는 경우
        if(num!=right){
            ans = Math.min(solve(idx+1, num, right)+cost[left][num], ans);   
        }
        
        //오른쪽 손가락을 움직이는 경우
        if(num!=left){
            ans = Math.min(solve(idx+1, left, num)+cost[right][num], ans);   
        }
        
        return dp[idx][left][right] = ans;
    }
    
    public void initCost() {
	
        //0~9까지 가중치 배열 초기화
        cost = new int[10][10];
    
        int r1, c1, r2, c2;
        
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j<10; j++) {
                if(i==j){
                    cost[i][j] = 1;
                    continue;
                }
                
                if(i==0) {
                    r1 = 3;
                    c1 = 1;
                }
                else{
                    r1 = (i-1)/3;
                    c1 = (i-1)%3;
                }
                if(j==0) {
                    r2 = 3;
                    c2 = 1;
                }
                else{
                    r2 = (j-1)/3;
                    c2 = (j-1)%3;
                }
                
                int dr = Math.abs(r1-r2);
                int dc = Math.abs(c1-c2);
                int min = Math.min(dr, dc);
                int max = Math.max(dr, dc);
                int diff = dr+dc;
                
                if(diff==1){
                    cost[i][j] = 2;
                }
                else if(diff>1){
                    cost[i][j] = min*3 + (max-min)*2;
                }
            }
        }
    }
}