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

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/136797?language=java

문제 풀이

• 해당 문제는 브루트포스를 이용할 경우 2^100000 경우의 수가 나오기 때문에 시간초과가 발생한다.
• 다이나믹 프로그래밍을 사용하였고 문제에 이용한 방식은 아래와 같습니다.

  1. 각 번호간의 최소 이동 코스트를 2차원 배열에 저장해둔다. (반복 계산 방지)
  2. solve (ind, L, R) 함수에서 왼쪽 손가락이나 오른쪽 손가락을 움직이되, 최소 가중치를 가지도록 한다.
  3. 이때, L, R의 위치가 같아지는 경우를 예외처리해준다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public 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 }
    };

    public int[][][] dp; //dp[ind][left][right]
    public String arr;
    public int len;
    
    public int solve(int ind, int L, int R) {
        //기저 조건 
        if (ind == len) {
            return 0;
        }
        if (dp[ind][L][R] != -1) return dp[ind][L][R];
        
        int num = arr.charAt(ind) - '0';
        int result = Integer.MAX_VALUE;
        
        //왼쪽 손가락으로 움직이기 
        if (num != R) result = Math.min(solve(ind+1, num, R) + cost[L][num], result);
        
        //오른 손가락으로 움직이기
        if (num != L) result = Math.min(solve(ind+1, L, num) + cost[R][num], result);
        return dp[ind][L][R] = result;
    }
    
    public int solution(String numbers) {
        arr = numbers;
        len = numbers.length();
        //초기화 
        dp = new int[len + 1][10][10];
        for (int i = 0; i < len + 1; i++) {
            for (int j = 0; j < 10; j++)
                Arrays.fill(dp[i][j], -1);
        }
        return solve(0, 4, 6);
    }
}