[백준] 13392번 방법을 출력하지 않는 숫자 맞추기

문제 설명

https://www.acmicpc.net/problem/13392

문제 풀이

• 다이나믹 프로그래밍으로 풀이하였다.
• 아래 점화식을 통해 메모이제이션하며 DFS를 진행했다.

  DP[N][이전 전체 회전수 % 10] : 이전 왼쪽 회전수가 정해져있을때, N번째 숫자부터 맞추기 위한 최소 회전값

소스 코드 (JAVA)

import java.util.*;
import java.io.*;

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static int N;
    static int[] source, target;
    static int[][] dp;

    public static int increase(int s, int diff) {
        return (s + diff) % 10;
    }

    public static int incDiff(int s, int e) {
        return e - s < 0 ? e - s + 10 : e - s;
    }

    public static int decDiff(int s, int e) {
        return s - e < 0 ? s - e + 10 : s - e;
    }

    public static int solve(int n, int rotate) {
        //기저 조건
        int cur = increase(source[n], rotate);
        if (n == N -1) return Math.min(incDiff(cur, target[n]), decDiff(cur, target[n]));
        if (dp[n][rotate] != -1) return dp[n][rotate];
        int incDiff = incDiff(cur, target[n]);
        int decDiff = decDiff(cur, target[n]);

        return dp[n][rotate] = Math.min(
                incDiff + solve(n+1, (incDiff + rotate) % 10),
                decDiff + solve(n+1, rotate)
        );
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        source = new int[N];
        target = new int[N];
        dp = new int[N][10];
        String in = br.readLine();
        for (int i = 0; i < N; i++)
            source[i] = Integer.parseInt(String.valueOf(in.charAt(i)));
        in = br.readLine();
        for (int i = 0; i < N; i++)
            target[i] = Integer.parseInt(String.valueOf(in.charAt(i)));
        for (int i = 0; i < N; i++)
            Arrays.fill(dp[i], -1);
    }

    public static void main(String[] args) throws IOException {
        input();
        bw.write(solve(0, 0) + "\n");
        bw.flush();
    }
}