문제 링크
문제
티어: 골드 1
알고리즘: dp
아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10개의 면을 가지고 있고, 각 면에는 오른쪽 방향으로 0, 1, 2, 3, …, 9까지의 숫자가 하나씩 순서대로 적혀 있다. 하나의 숫자나사를 왼쪽으로 회전 시키면, 이 나사보다 아래에 위치한 모든 나사는 같이 따라서 돌게 되지만, 나사를 오른쪽으로 회전시키면, 다른 나사는 함께 돌지는 않는다. 정면에서 보아 위에서부터 아래쪽으로 숫자를 읽어 내려간다고 할 때, 현재의 상태에서 가장 적은 칸수의 움직임으로 원하는 숫자를 만들기 위한 방법을 출력하는 프로그램을 작성하라.
예를 들어 세 개의 숫자나사가 주어졌을 때, 정면에서 보는 현재 상태가 326이고 원하는 상태는 446이라면 최소 회전 칸수는 4이다. 먼저 숫자나사 1을 왼쪽으로 한 칸 돌리면 437이 되고, 숫자나사 2를 역시 왼쪽으로 한 칸 돌리면 448이 되며, 마지막으로 숫자나사 3을 오른쪽으로 두 칸 돌리면 446이 된다.
입력
첫째 줄에는 숫자나사의 개수 N이 주어지고, 둘째 줄에는 현재의 상태가, 셋째 줄에는 원하는 상태가 주어진다. N은 3 이상이고 10,000 이하이다.
출력
첫째 줄에는 현재 상태에서 원하는 상태로 도달하는데 필요한 최소 회전 칸수를 출력한다.
풀이
현재 상태에서 원하는 상태로 도달하는데 필요한 최소 회전 칸수를 출력해야 한다.
먼저, 숫자나사 1을 원하는 수로 맞춰주기 위해서 어떻게 해야될까?
그 밑에 숫자나사 2, 3, .., N으로는 맞춰줄 수 없다.
숫자나사 1을 직접 회전시켜야 한다.
숫자나사 1을 회전시키는 방법은 다양한 경우의 수가 있을 것이다.
그런데 생각해 보면 왼쪽으로 회전하는 경우 오른쪽으로 회전하다가 왼쪽으로 회전할 필요가 있을까? 그 반대도 마찬가지다.
타겟 숫자를 맞춰주면서 왼쪽 회전 횟수를 증가 시켜줄 수는 있어도 그렇게 할 필요가 없다.
왼쪽 회전 횟수를 증가시키는 것은 나머지 숫자나사들을 같이 돌리기 위함일 것인데, 밑에 숫자나사로 돌려도 그 횟수는 같으며 오히려 불필요한 회전이 전체 횟수를 증가시키기만 할 것이다.
그래서 방향만 정하면 되기 때문에 두 가지 경우의 수만 존재한다.
- 왼쪽으로 돌리는 경우
- 오른쪽으로 돌리는 경우
그런데 왼쪽, 오른쪽으로 dp를 정의한다면 경우의 수는 2^10000일 것이다.
중복된 상태를 찾아줘야 하는데, 생각해보면 왼쪽으로 회전하는 경우 그 밑에 숫자나사도 같이 돌아가기 때문에 각 숫자나사에서 위와 현재 위치에서 왼쪽으로 회전한 횟수의 합이 그 밑에 모든 숫자나사가 왼쪽으로 회전한 횟수가 될 것이다.
그래서 각 숫자나사의 상태는 현재까지 왼쪽으로 회전한 횟수가 경우의 수가 되며, 상태가 같은 경우 작은 값으로 업데이트 해주면 된다.
그러면 왼쪽으로 회전한 횟수는 최대 몇 일까? 단순히 회전 횟수로만 한다면 시간 초과가 난다.
만약 10번 회전했다면, 그 위치에 수는 0번 회전했을 때의 수와 같을 것이다.
그래서 회전 횟수는 0 ~ 9까지만 따져주면 된다.
이를 토대로 dp를 정의하면 다음과 같다.
int[][] dp = new int[N + 1][9 + 1]; //dp[A][B]- A는 각 숫자 나사를 의미하며
- B는 0 ~ 9번까지의 회전 횟수를 의미한다.
이후에는 숫자나사 1부터 숫자나사 N까지 돌면서 전 숫자나사 회전 횟수의 왼쪽, 오른쪽 회전하는 경우를 구하고, 현 숫자나사 회전횟수를 최소값으로 업데이트해 나가면 최소 회전 칸수를 구할 수 있다.
이 풀이의 시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static final int MAX = 1000000;
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] dp = new int[N + 1][10];
init(dp);
int[] cur = new int[N + 1];
int[] target = new int[N + 1];
initState(br.readLine(), cur);
initState(br.readLine(), target);
int left1 = calRotation(cur[1], target[1], true);
dp[1][left1] = left1;
dp[1][0] = calRotation(cur[1], target[1], false);
for(int i=2; i<=N; i++) {
for(int j=0; j<=9; j++) {
if(dp[i - 1][j] != MAX) {
//가능한 경우
int curNum = rotation(cur[i], j);
int left = calRotation(curNum, target[i], true);
int nextLeft = rotation(j, left);
dp[i][nextLeft] = Math.min(dp[i][nextLeft], dp[i - 1][j] + left);
int right = calRotation(curNum, target[i], false);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + right);
}
}
}
int answer = MAX;
for(int i=0; i<=9; i++) {
answer = Math.min(answer, dp[N][i]);
}
System.out.println(answer);
}
static void init(int[][] arr) {
for(int i=1; i<=N; i++) {
for(int j=0; j<=9; j++) {
arr[i][j] = MAX;
}
}
}
static void initState(String str, int[] arr) {
for(int i=0; i<str.length(); i++) {
arr[i + 1] = str.charAt(i) - '0';
}
}
static int rotation(int c, int cnt) {
//c에서 cnt만큼 왼쪽으로 회전한 경우 나오는 수
return (c + cnt) % 10;
}
static int calRotation(int c, int t, boolean left) {
if(c == t) {
return 0;
}
if(left) {
//왼쪽으로 돌리는 경우 수가 증가함
if(c < t) {
return t - c;
}
//c가 더 큰 경우
return (t + 10) - c;
}
//오른쪽으로 돌리는 경우 수가 감소함
if(c > t) {
return c - t;
}
return (c + 10) - t;
}
}