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

문제

N자리 숫자 자물쇠가 있다. 각 자릿수는 0~9로 이루어져 있으며 위아래로 회전할 수 있다. 인접한 자릿수를 함께 움직이거나 단독으로 움직일 수 있다. 현재 상태에서 목표 상태로 만들기 위한 최소 회전 횟수를 구하는 문제이다.

각 자릿수는 독립적으로 돌리거나, i번째와 i+1번째를 동시에 돌릴 수 있다.

입력

첫째 줄에 자릿수의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 현재 자물쇠 상태 S가 주어진다. 셋째 줄에 목표 자물쇠 상태 T가 주어진다.

출력

최소 회전 횟수를 출력한다.

예제

입력	출력
`4` `9999` `1111`	`12`

풀이

각 자릿수에서 이전 자릿수와 함께 돌렸을 때의 여파(carry)를 DP 상태로 표현하여 풀이한다.

dp[i][j]를 i번째 자릿수까지 처리했을 때, i번째 자릿수에 carry j(0~9)가 남아있는 상태의 최소 비용으로 정의한다.
i번째 자릿수에서 필요한 회전 수 diff = (arr[i] - res[i] - carry + 20) % 10을 계산한다.
이전 자릿수에서 carry j가 발생했을 때, 추가로 독립 회전 수를 더한 값을 다음 자릿수로 전파한다.
각 자릿수에서 carry를 0~19까지 적용하며 최솟값을 갱신한다.
최종 dp[N][0]이 답이다.

핵심 아이디어: 인접한 자릿수를 함께 돌릴 때 발생하는 "다음 자릿수에 대한 여분 회전(carry)"을 DP 상태로 포함한다. dp[i][j]에서 j가 현재 carry이고, 실제로 필요한 회전 수에서 carry를 빼고 나머지를 처리한다.

코드

package com.ssafy.an.day149;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Day147BOJ13392DP { // 13392 DP 구선생님
	static int N;
	static int[] arr, res;
	static int[][] dp;
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1];
		res = new int[N + 1];
		dp = new int[N + 1][10];
 
		String str1 = br.readLine();
		String str2 = br.readLine();
 
		for (int i = 0; i < N; i++) {
			arr[N - i] = str1.charAt(i) - '0';
			res[N - i] = str2.charAt(i) - '0';
		}
 
		for (int i = 1; i < N + 1; i++) {
			for (int j = 0; j < 10; j++)
				dp[i][j] = dp[i - 1][j] + (arr[i] - res[i] - j + 20) % 10;
			for (int j = 1; j < 20; j++)
				dp[i][j % 10] = Math.min(dp[i][j % 10], dp[i][(j - 1) % 10] + 1);
		}
 
		System.out.println(dp[N][0]);
		br.close();
	}
}

복잡도

시간: O(N) — 각 자릿수에서 carry 0~19 처리 (상수 시간)
공간: O(N)

문제

각 자릿수는 독립적으로 돌리거나, i번째와 i+1번째를 동시에 돌릴 수 있다.

입력

첫째 줄에 자릿수의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 현재 자물쇠 상태 S가 주어진다. 셋째 줄에 목표 자물쇠 상태 T가 주어진다.

출력

최소 회전 횟수를 출력한다.

예제

입력	출력
`4` `9999` `1111`	`12`

풀이

각 자릿수에서 이전 자릿수와 함께 돌렸을 때의 여파(carry)를 DP 상태로 표현하여 풀이한다.

dp[i][j]를 i번째 자릿수까지 처리했을 때, i번째 자릿수에 carry j(0~9)가 남아있는 상태의 최소 비용으로 정의한다.

i번째 자릿수에서 필요한 회전 수 diff = (arr[i] - res[i] - carry + 20) % 10을 계산한다.

이전 자릿수에서 carry j가 발생했을 때, 추가로 독립 회전 수를 더한 값을 다음 자릿수로 전파한다.

각 자릿수에서 carry를 0~19까지 적용하며 최솟값을 갱신한다.

최종 dp[N][0]이 답이다.

코드

package com.ssafy.an.day149;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Day147BOJ13392DP { // 13392 DP 구선생님
	static int N;
	static int[] arr, res;
	static int[][] dp;
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1];
		res = new int[N + 1];
		dp = new int[N + 1][10];
 
		String str1 = br.readLine();
		String str2 = br.readLine();
 
		for (int i = 0; i < N; i++) {
			arr[N - i] = str1.charAt(i) - '0';
			res[N - i] = str2.charAt(i) - '0';
		}
 
		for (int i = 1; i < N + 1; i++) {
			for (int j = 0; j < 10; j++)
				dp[i][j] = dp[i - 1][j] + (arr[i] - res[i] - j + 20) % 10;
			for (int j = 1; j < 20; j++)
				dp[i][j % 10] = Math.min(dp[i][j % 10], dp[i][(j - 1) % 10] + 1);
		}
 
		System.out.println(dp[N][0]);
		br.close();
	}
}