BOJ) 방법을 출력하지 않는 숫자 맞추기

방법을 출력하지 않는 숫자 맞추기

13392번: 방법을 출력하지 않는 숫자 맞추기

풀이

 

매우 어려웠던 문제였다. DP를 이용하는 문제이고, left와 right를 각각 저장하면서 진행해야한다는 것까지는 눈치를 챘다.

하지만, 계속되는 오답과 시간초과에 멘붕이 왔다.

다른 분들의 풀이를 참고하기로 했다.

저장하는 DP를 이동 뿐만 아니라, 큐브의 숫자인 0~9에 대해 저장해주는 것이었다.

이에 대해 이해하기는 했지만, 가까운 미래까지는 이 생각에 도달하지는 못할 것 같았다.

그래서, 이런 방법으로 푸는 거구나... 기억하기 위해 포스팅에 남긴다.

 

2차원 dp의 크기는 입력받은 숫자나사의 갯수만큼, 0~9를 담기 위해 10만큼 할당을 해준다.

모든 배열에는 최대 값을 저장해둔다. (이후 로직에서 최소값을 저장하기 위함 ~> 초기값 0이면 계속 0만 최소값이 되기 때문)

첫 시작이 0에서 시작한다는 가정에, dp[0]의 각 인덱스(0~9) 에는 각 숫자만큼 가기 위한 left 회전 수를 저장해준다.

 

이후, 입력받은 나사를 돌면서, dp의 이전 인덱스에서 right 회전이 최소가 되는지, left 회전이 최소가 되는지 저정해나간다.

숫자 나사의 마지막 depth에 대해 0~9까지 최소 값을 찾아준다.

(이 두 부분을 아직 잘 모르겠음)

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class NumberCube_13392 {
    final static int ZERO = 48, MAX = 10;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int size = Integer.parseInt(br.readLine());
        int[] cube = new int[size+1];
        int[] target = new int[size+1];

        String str1 = br.readLine();
        String str2 = br.readLine();

        for(int i=1; i<=size; i++) {
            cube[i] = str1.charAt(i-1)-ZERO;
            target[i] = str2.charAt(i-1)-ZERO;
        }
        br.close();

        System.out.println(solution(cube,target));
    }

    private static int solution(int[] cube, int[] target) {
        int[][] dp = new int[cube.length][10];
        for(int i=0; i<cube.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for(int i=0; i<MAX; i++) {
            dp[0][i] = i;
        }
        for(int i=1; i<cube.length; i++) {
            for(int j=0; j<MAX; j++) {
                int left = (target[i] - cube[i] -j +20)%10;
                int right = 10-left;
                dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + right);
                dp[i][(j+left)%MAX] = Math.min(dp[i][(j+left)%MAX], dp[i-1][j] + left);
            }
        }
        int answer = dp[cube.length-1][0];

        for(int i=1; i<MAX; i++) {
            answer = Math.min(answer, dp[cube.length-1][i]);
        }
        return answer;
    }
}