BOJ_1514_자물쇠 (Java)

[Platinum III] 자물쇠 - 1514

문제 링크

성능 요약

메모리: 18068 KB, 시간: 144 ms

분류

다이나믹 프로그래밍, 그래프 이론, 최단 경로

제출 일자

2025년 9월 3일 03:35:58

문제 설명

세준이는 노트북을 누가 가져갈까봐 자물쇠로 잠가놓는다. 자물쇠는 동그란 디스크 N개로 구성되어 있다. 각 디스크에는 숫자가 0부터 9까지 숫자가 표시되어 있다. 디스크는 원형이기 때문에, 0과 9는 인접해 있다.

세준이는 한 번 자물쇠를 돌릴 때, 최대 세 칸을 시계 방향 또는 반시계 방향으로 돌릴 수 있다. 또, 최대 세 개의 인접한 디스크를 한 번에 돌릴 수 있다.

현재 자물쇠의 상태와 세준이의 비밀번호가 주어질 때, 자물쇠를 최소 몇 번 돌려야 풀 수 있는지 구하는 프로그램을 작성하시오.

자물쇠의 상태가 555이고, 세준이의 비밀번호가 464인 경우에, 각 디스크를 따로 따로 돌리면 3번 돌려야 한다. 하지만, 디스크 3개를 동시에 돌려서 444로 만들고, 2번째 디스크를 6으로 돌리면 2번만에 돌릴 수 있다.

입력

첫째 줄에 세준이의 비밀번호의 길이 (자물쇠의 크기) N이 주어진다. N은 100보다 작거나 같다. 둘째 줄에 현재 자물쇠의 상태가 주어지고, 셋째 줄에 세준이의 비밀번호가 주어진다.

출력

첫째 줄에 최소 몇 번을 돌려야 풀 수 있는지 구하는 프로그램을 작성하시오.

문제 풀이

이 문제는 동적 계획법(DP)으로 해결할 수 있다. 핵심은 현재 인덱스부터 끝까지 최소 회전 횟수를 재귀적으로 계산하고, 이미 계산한 상태는 메모이제이션하여 재사용하는 것이다. DP의 상태는 현재 디스크와 다음 두 디스크의 값으로 정의한다. 이는 한 번에 최대 세 개 디스크를 돌릴 수 있기 때문이다. 따라서 dp[currIdx][x][y][z]는 currIdx 위치부터 끝까지, 현재 디스크 값이 x, 다음 디스크 값이 y, 그 다음 디스크 값이 z일 때 최소 회전 횟수를 의미한다.

재귀 함수에서 먼저 현재 디스크가 목표 값까지 얼마나 돌려야 하는지 계산한다. 시계 방향과 반시계 방향 두 가지 경우를 모두 고려하며, 가능한 조작을 세 가지로 나누어 탐색한다. 첫 번째 디스크만 돌리는 경우, 첫 번째와 두 번째 디스크를 함께 돌리는 경우, 세 디스크 모두를 돌리는 경우이다. 각 조작에서 필요한 회전 수를 3으로 나누어 올림하면 실제 회전 횟수를 계산할 수 있다. 이 과정을 통해 단순히 자리별 회전 수를 더하는 방식보다 훨씬 효율적으로 최소 횟수를 구할 수 있다.

구현할 때는 배열 범위 문제를 고려하여 start 배열의 크기를 N+3으로 설정하였다. 이렇게 하면 currIdx + 3 접근 시 안전하게 값을 가져올 수 있다. DP 배열은 -1로 초기화하여 이미 계산된 상태를 재사용하도록 하였다. 이를 통해 동일한 상태를 반복적으로 계산하는 비효율을 피할 수 있다.

최종적으로 시작 인덱스 0에서 목표 상태까지 solve(0, start[0], start[1], start[2])를 호출하면 최소 회전 횟수를 얻을 수 있다. 이 접근법은 문제의 조건을 모두 반영하면서도 계산량을 크게 줄여, N이 최대 100일 때도 효율적으로 동작한다.

결과적으로, 이번 문제를 통해 한 번에 여러 자리를 동시에 돌릴 수 있는 경우에는 단순 계산보다 DP로 상태를 관리하는 것이 효율적이라는 알고리즘 설계 원리를 확인할 수 있다.

코드

package BOJ_1514_자물쇠;

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[] start, end;
	static int[][][][] dp;
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		//br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1514_자물쇠/input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		String s = br.readLine();
		String e = br.readLine();

		start = new int[103];
		end = new int[103];

		for (int i = 0; i < N; i++) {
			start[i] = s.charAt(i) - '0';
			end[i] = e.charAt(i) - '0';
		}

		dp = new int[101][10][10][10];
		for (int i = 0; i < 101; i++) {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 10; k++) {
					Arrays.fill(dp[i][j][k], -1);
				}
			}
		}

		System.out.println(solve(0, start[0], start[1], start[2]));

		bw.flush();
		bw.close();
		br.close();
	}

	/**
	 * @param currIdx 현재 맞추고 있는 인덱스 (0 ≤ currIdx < N)
	 * @param x       현재 위치(currIdx)에 있는 디스크의 숫자 (0~9)
	 * @param y       다음 위치(currIdx+1)에 있는 디스크의 숫자 (0~9)
	 * @param z       그 다음 위치(currIdx+2)에 있는 디스크의 숫자 (0~9)
	 * @return currIdx부터 끝까지 목표 상태(end[])로 맞추는 데 필요한 최소 조작 횟수
	 *
	 * <p>설명:
	 * <ul>
	 *   <li>한 번의 조작에서 최대 세 개 연속 디스크를 같은 방향으로 최대 3칸까지 돌릴 수 있다.</li>
	 *   <li>현재 자리 x를 end[currIdx]에 맞추기 위해 필요한 칸 수를 왼쪽/오른쪽 두 방향으로 모두 고려한다.</li>
	 *   <li>필요한 칸 수를 (x만 돌림, x+y 돌림, x+y+z 돌림)으로 분배하여 최소 조작 횟수를 계산한다.</li>
	 *   <li>dp[currIdx][x][y][z]에 메모이제이션하여 동일 상태의 중복 연산을 방지한다.</li>
	 * </ul>
	 */
	private int solve(int currIdx, int x, int y, int z) {
		if (currIdx == N) return 0;

		if (dp[currIdx][x][y][z] != -1) return dp[currIdx][x][y][z];

		int res = Integer.MAX_VALUE;

		int diff = (end[currIdx] - x + 10) % 10;
		int[] ableDiffs = {diff, 10 - diff}; // {시계방향 회전수, 반시계방향 회전수}

		for (int i = 0; i <= 1; i++) { // x 디스크는 i=0 시계, i=1 반시계
			for (int j = 0; j <= ableDiffs[i]; j++) { // y 디스크는 0~ableDiffs[i] 만큼
				for (int k = 0; k <= j; k++) { // z 디스크는 0~j 만큼
					int next_y = (y + (i == 0 ? j : -j) + 10) % 10;
					int next_z = (z + (i == 0 ? k : -k) + 10) % 10;

					int rot = solve(currIdx + 1, next_y, next_z, start[currIdx + 3]);

					// 최소 돌린횟수 = 세개 나눠서 돌린 횟수 (xyz돌리기 + xy돌리기 + x돌리기)
					rot += (k + 2) / 3 + ((j - k) + 2) / 3 + ((ableDiffs[i] - j) + 2) / 3;
					res = Math.min(res, rot);
				}
			}
		}

		return dp[currIdx][x][y][z] = res;
	}
}