디지털 카운터

---

🔗 🔗 전체 1020번 문제

조건

---

문제

---

지민이는 매 초마다 수가 증가하는 $N$자리의 디지털 카운터를 가지고 있다. 카운터에 나오는 수는 순환된다. $10^{N - 1}$에 이르면 다시 0부터 시작한다.

각 숫자는 다음과 같은 7개의 선분으로 이루어져 있다.

INPUT
1
2
3
4
5
6
7
8
9
10
11
    +   +---+   +---+   +   +   +---+
    |       |       |   |   |   |
    +   +---+   +---+   +---+   +---+
    |   |           |       |       |
    +   +---+   +---+       +   +---+

+---+   +---+   +---+   +---+   +---+
|           |   |   |   |   |   |   |
+---+       +   +---+   +---+   +   +
|   |       |   |   |       |   |   |
+---+       +   +---+       +   +---+

모든 인접한 두 개의 선분은 $+$로 이어져 있다. 예를 들어, 1은 두 개의 선분, 9는 다섯 개의 선분으로 이루어져 있다.

현재 카운터에 나와있는 숫자가 주어진다. 그럴 때, 현재 나와있는 숫자의 선분의 개수와 같은 숫자는 최소 몇 초가 지나야 나오는지 구하는 프로그램을 작성하시오.

1, 2, ..., 9, 그리고 0은 모두 2, 5, 5, 4, 5, 6, 3, 7, 5, 6개의 선분으로 이루어져 있고, 모든 수는 $N$자리를 채워야 하므로, $N$자리보다 작을 때는 앞에 0이 있을 수도 있다.

입력

---

첫째 줄에 현재 카운터에 나와있는 수가 주어진다. $N$은 그 수의 길이와 같다. (수가 0으로 시작할 수도 있음) 그리고, $N$은 15보다 작거나 같은 자연수이다.

출력

---

첫째 줄에 최소 몇 초가 지나야 현재 카운터에 나와 있는 수와 선분의 개수가 같아지는지 출력한다.

케이스

---

예제 1

---

INPUT
1
007

OUTPUT
1
11

풀이

---

문제 이해하기

---

문제 이해도는 그리 높지 않다. 디지털 계산기를 생각해보자.

숫자를 표현하는데 여러 개의 선분이 필요하며, 문제의 기호보다 위 그림을 보면 쉽게 이해할 수 있을 것이다. 각 숫자를 표현하는데 필요한 숫자를 표로 정리하면 아래와 같다.

특징 1

---

임의의 숫자 02를 표현하는데 필요한 선분의 갯수는 각각 6개와 5개로, 11개의 선분이 필요하다.

숫자는 1초마다 바뀌며, 선분의 합이 11개가 되는 숫자가 몇 초 뒤에 나오는지를 계산하면 된다. 선분의 합이 11개인 가장 가까운 수는 03으로, 1초가 걸린다.

만약 정해진 자릿수의 최대를 넘어가면 0부터 다시 돌아와 카운팅한다. 즉, 02의 경우 두 자리이므로, 99를 넘어서면 다시 00으로 되돌아간다.

특징 2

---

이번엔 임의의 숫자 98의 케이스를 생각해보자. 주어진 숫자가 두 자리이므로, $N = 2$임을 알 수 있다. 98을 표현하는데 필요한 선분의 갯수는 각각 7과 5로, 12개의 선분이 필요하다.

99 역시 총 10개의 선분으로 이루어지므로 답이 되지 못하며, 두 자리 수의 최대값은 99이므로 00으로 넘어가서 값을 찾는다. 오버플로우(Overflow)의 개념과 동일하다.

0은 6개의 선분으로 이루어져 있으므로, 00을 표현하는데 필요한 선분의 갯수는 12개다. 즉, 답은 2초가 된다.

이렇게 정해진 자릿수를 초과할 경우 또한 계산해야한다.

다이나믹 프로그래밍 적용하기

---

문제의 요구사항도 직관적이고, 특징 또한 그리 복잡하지 않다. 순수히 문제에서 요구하는 로직 자체가 어렵다.

숫자의 자릿수가 최대 15자리(100조)에 육박하므로, 이렇게 많은 양의 데이터를 빠르게 처리하는데는 다이나믹 프로그래밍이 적절할 것이다.

또한 int는 약 21억까지만 다룰 수 있으므로, long 데이터를 써야함을 짐작할 수 있다.

그 어떤 고려사항 없이 무식하게 접근한다면 그리 어렵지 않을 것이다. 숫자를 하나하나 분리해서 선분의 갯수를 구하여 합한 다음, 현재 숫자부터 1씩 증가시키며 위 계산을 반복하면 될 것이다. 물론 그렇게 쉬웠다면 내가 일주일 넘게 고민하지도 않았겠지만.

다이나믹 프로그래밍은 이분 매칭과 같은 특정한 패턴이 있는게 아닌 개념에 가까워서, 이를 적절히 적용할 수 있는 접근 방식(점화식 등)을 도출해야한다.

원리 이해하기

---

이 알고리즘의 핵심은 선분의 합이다. 하나의 숫자를 표시하는데 필요한 선분의 수는 2 ~ 7 사이의 값을 가진다. 동일한 선분의 갯수를 가지는 숫자가 있으므로 일부 겹친다.

만약 하나의 숫자를 통해 만들 수 있는 선분의 합을 나열하고, 이 합을 가질 수 있는 숫자들 중 가장 작은 수를 표시하면 아래와 같다.

예를 들어, 선분의 갯수가 5인 숫자는 [ 2, 3, 5, 9 ]로 4개가 존재한다. 그 중 가장 작은 수는 4이므로 위 표의 5에는 2가 매칭된다.

위 표는 한 자릿수에서 나올 수 있는 경우의 수다. 만약 두 자릿수를 기준으로 표를 도식하면 아래와 같다. 한 자릿수에서의 최소값이 2, 최대값이 7이므로, 두 자릿수에서는 4 ~ 14의 범위를 가짐을 유추할 수 있다.

위처럼 나타낼 수 있다. 두 자릿수에서 선분의 합이 11인 수는 02가 가장 작음을 바로 찾을 수 있다.

이러한 원리를 통해 자릿수를 하나하나 넓혀가며 동일한 선분을 가지는 값을 빠르게 찾을 수 있다.

예를 들어, 0598와 동일한 선분의 수를 갖는 가장 가까운 수를 찾아보자. 0598의 선분합은 6 + 5 + 5 + 7 =

23

이다. 즉, 0598과 가장 가까우면서 선분의 합이 23인 숫자를 찾으면 된다.

1. 1의 자리 비교하기

1의 자리를 비우면 059_와 같이 표기할 수 있다. 8의 선분값은 7이므로 _에 0부터 9까지 순차적으로 대입하여 선분값이 7이 되는 수를 찾는다. 단, 원래의 값인 8은 탐색 대상에서 제외한다.

선분의 합이 7이 되는 한 자릿수는 8 이외엔 없으므로, 1의 자리에선 동일한 선분합을 갖는 숫자가 자신 이외에 없다.

따라서 1의 자리 조합으로는 만족하는 수를 찾을 수 없다.

2. 10의 자리 비교하기

10의 자리를 비우면 05_X와 같이 표기할 수 있다. _는 0부터 9까지 대입할 자리이며, X은 해당 자리에서 나올 수 있는 선분의 합을 가지는 가장 작은 수가 대입된다.

즉, X는 위 표에 해당하는 0, 1, 2, 4, 7, 8만 올 수 있다.

• _ 0 ~ 9
• X 0, 1, 2, 4, 7, 8

_와 X의 합이 8, 9의 선분합과 동일하면 된다. 따라서 선분의 합이 12가 되는 조합을 찾는다.

0500, 0528, 0538, 0558, 0560, 0582, 0598이 후보군이다.

하지만 0598은 자기 자신으로 제외되며, 나머지 숫자 모두 조건은 맞지만, 0598보다 작다. 한 사이클을 돌아야 나오는 수이므로, 아직 속단하긴 이르다.

3. 100의 자리 비교하기

100의 자리를 비우면 0_XX와 같이 표기할 수 있다.

즉, XX는 위 표에 해당하는 00, 01, 02, 04, 07, 08, 11, 12, 14, 17, 88만 올 수 있다.

• _ 0 ~ 9
• X 00, 01, 02, 04, 07, 08, 11, 12, 14, 17, 88

_와 XX에 값을 각각 대입해봄으로써 5, 8, 9의 선분합인 17을 가지는 수를 찾는다.

0002, 0200, 0300, 0408, 0500, 0602, 0788, 0804, 0900이 후보군이다.

이 중 0602는 입력값인 0598과 4만큼 차이가 나므로 선분의 갯수가 동일한 가장 가까운 수다.

얼고리즘이 요구하는 답은 선분의 갯수가 동일한 가장 가까운 수가 나오는데 걸리는 시간이다. 각 숫자는 1초마다 바뀌므로, 0598에서 0602가 되는데 걸리는 시간 4가 답이 된다.

DP배열 만들기

---

위 예제의 경우 0598의 선분합을 구하고, 0599부터 하나하나 계산하면서 나아가면 쉽게 풀 수 있을 것이다. 하지만 이 방식은 매우 비효율적이기 때문에 알고리즘의 취지와는 맞지 않다.

한 자릿수, 두 자릿수에서 나올 수 있는 선분합의 최소값을 가지는 수를 정리하면 아래와 같다.

• 한 자릿수

• 두 자릿수

위 표의 값들을 계산하여 하나의 표로 만들면 메모이제이션을 적용할 수 있을 것이다.

메모이제이션을 적용할 배열 dp[i][j]가 있다고 가정하자. 각 인덱스의 의미는 아래와 같다.

• $i$: 자릿수 $(i = 1, 2, \, \, \, \dotsm \, \, \, , 14, 15)$
• $j$: 선분의 합

※ i와 j엔 0이 오지 않는다. 이유는 후술

• $dp[1][6]$: 선분의 합이 6인 한자리 수 중 가장 작은 수
• $dp[2][12]$: 선분의 합이 12인 두자리 수 중 가장 작은 수
• $dp[n][m]$: 선분의 합이 m인 n자리 수 중 가장 작은 수

만약 $dp[3][6]$을 구할 경우, 세 자릿수의 선분 합이 6인 숫자의 최소값이므로 111(2 + 2 + 2)가 된다. 이렇게 적절한 값이 나올 수 있도록 배열 dp의 표현식을 도출해야한다.

DP배열 예시

---

DP배열의 예시는 아래와 같다.

세 자리 숫자를 기준으로 계산한 DP배열은 위와 같다. 자릿수를 기준으로 $i$값이 비례해서 늘어난다. 하지만 배열의 값은 고정적으로, 숫자가 변한다고 해서 DP배열의 값이 이에 따라 변하지 않는다.

쉽게 말하면 0598과 135 숫자를 입력값으로 했을 때, dp[2][7]은 둘 다 12로 동일하다.

DP배열 크기 선언하기

---

알고리즘에서의 자릿수는 $N$이므로, dp의 크기를 식으로 표현하면 아래와 같다.

JAVA
1
2
3
long[] dp = new long[N + 1][(N * 7) + 1];

Arrays.fill(arr, Long.MAX_VALUE);

요소의 값이 크므로 long 배열로 선언한다. 배열 dp는 가급적 적절한 큰 값으로 초기화를 진행해준다.

본 문서에서는 long의 최대값인 Long.MAX_VALUE로 배열 전체를 초기화한다.

JAVA
1
private static final int[] FLAG = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 5 };

숫자 선분의 갯수 또한 코드화한다. FLAG는 각 해당 인덱스 숫자가 가지는 선분의 합을 반환한다.

FLAG[2]는 숫자 2의 선분합으로, 5를 반환한다.

$N = 3$일 경우, 세 자릿수를 가지며, 선분 합의 최대값은 21이다. 이를 배열로 초기선언하면 new long[3][21]로 표현할 수 있겠지만, 컴퓨터 언어의 특성으로 혼란이 생긴다.

대부분의 컴퓨터 언어는 배열의 시작을 0으로 본다. 위와 같이 선언한 매열에서 두 자릿수를 가지며, 선분 합이 10인 값을 호출하려면 dp[2][10]이 아니라 dp[1][9]를 호출해야한다.

특히 이렇게 복잡한 문제의 경우 변수를 사용하는 과정에서 많은 혼란을 야기할 수 있기 때문에, 가급적 서로 맞춰주는 것이 중요하다. 이를 위해 첫 인덱스인 0을 사용하지 않고 각 선언 크기에 1을 더하여 범위를 증가시킨다음, 시작 인덱스를 1로 사용한다.

즉, 해당 문제에서 $i$와 $j$가 0인 배열은 사용하지 않으며, 어떤 의미도 가지지 않는다.

DP배열 초기값 지정하기

---

다이나믹 프로그래밍은 원래라면 처음부터 다시 계산해야하는 복잡한 과정을 생략하고, 이전에 계산된 내용을 토대로 추가적인 계산을 수행한다.

초기엔 로직에 따른 정석적인 계산을 하지만, 이후 계산값을 누적하고 이를 활용하여 다음 값을 계산한다. 특히 데이터의 양이 많으면 많을 수록 속도에서의 우위를 가져갈 수 있다.

따라서 다이나믹 프로그래밍은 초기값 설정도 매우 중요하다. 여기서의 초기값은 한 자리수에서 나올 수 있는 선분합의 조합으로 정의할 수 있다.

위 표를 배열 dp에 입력하면 된다. 한 자리 숫자이므로 $i = 1$로 고정이며, $j$는 선분합이다. 값은 그 숫자다.

JAVA
1
2
3
4
5
6
dp[1][2] = 1
dp[1][3] = 7
dp[1][4] = 4
dp[1][5] = 2
dp[1][6] = 0
dp[1][7] = 8

위처럼 선언해주면 된다.

하드코딩이 마음에 안 든다면, 아래처럼 사용하는 방법도 있다.

JAVA
1
2
3
4
for (int i = 0; i < FLAG.length; i++)
{
	dp[1][FLAG[i]] = Math.min(dp[1][FLAG[i]], i);
}

0부터 FLAG의 배열을 순차적으로 돌면서 해당 선분값을 가지는 가장 작은 값을 초기값으로 할당하게 된다.

DP배열 전개하기

---

지정한 초기값을 토대로 배열 dp의 값을 전개한다. 한 자릿수는 2 ~ 7 사이의 값을 가진다.

그렇다면, 두 자릿수는 한 자릿수의 조합이므로, 4 ~ 14 사이의 값을 가질 것이다.

즉, 자릿수별로 유효한 DP배열의 범위는 아래와 같다.

$$n \text{의 자리 범위} = (n - 1) * 2 \,\,\, \sim \,\,\, (n - 1) * 7$$

각 자릿수 별로 위 범위만큼만 신경쓰면 된다.

한 자릿수에서 할당된 숫자는 0, 1, 2, 4, 7, 8로 여섯 가지가 존재한다. 두 자릿수 또한 이 숫자들의 조합으로만 이루어진다.

따라서 00, 01, 02, ~ 84, 87, 88을 조합하여 선분의 합을 가지는 가장 작은 수를 dp에 할당한다.

예를 들어, dp[2][8]의 경우 01, 10, 44 등의 숫자 조합이 올 수 있다. 그 중 가장 작은 수는 01이므로, dp[2][8] = 1이 될 것이다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
for (int n = 2; n < dp.length; n++)
{
	for (int i = 2; i < 8; i++)
	{
		int start = (n - 1) * 2;
		int end = (n - 1) * 7 + 1;
		
		for (int j = start; j < end; j++)
		{
			dp[n][i + j] = Math.min(dp[n][i + j], (long) Math.pow(10, n - 1) * dp[1][i] + dp[n - 1][j]);
		}
	}
}

따라서 이를 식으로 표현하면 위와 같다.

• $n$: 자릿수
• $i$: $n$의 자리에 할당될 수의 선분합
• $j$: 남은 자리에 할당될 수의 선분합

$n$은 자릿수로써, 일의 자리는 일전에 이미 계산했으므로 2부터 시작한다.

start, end는 $n$의 자리 범위를 코드로 나타낸 것이다.

$i$와 $j$는 각각의 선분합으로, 위의 예시에서 설명한 0_XX에서 $i$는 _, $j$는 XX의 선분합이라 생각하면 된다.

dp[n][i + j]와 Math.pow(10, n - 1) * dp[1][i] + dp[n - 1][j] 중 더 작은 값을 dp 배열에 할당한다.

이를 배열이 끝날 때까지 반복하면 DP배열이 완성된다.

전체 소스

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 백준 전체 1020 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/08/24/a1020">1020 풀이</a>
 * @since 2021.07.06 11:36:34
 */
public class Main
{
	// 숫자 선분 갯수
	private static final int[] FLAG = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 5 };
	
	// 메모이제이션 배열
	private static long[][] dp;
	
	// 입력 숫자
	private static long number;
	
	// 자리별로 분리된 숫자 배열
	private static int[] numbers;
	
	// 숫자 자릿수
	private static int N;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 입력값
		String input = reader.readLine();
		
		number = Long.parseLong(input);
		
		numbers = Arrays.stream(input.split("")).mapToInt(Integer::parseInt).toArray();
		
		N = numbers.length;
		
		putDP();
		
		long result = solve();
		
		writer.write(String.valueOf(result));
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * DP 채우기 함수
	 */
	private static void putDP()
	{
		dp = new long[N + 1][(N * 7) + 1];
		
		// 전체 배열을 long의 최대값으로 초기화
		for (long[] arr : dp)
		{
			Arrays.fill(arr, Long.MAX_VALUE);
		}
		
		// 초기값 설정
		for (int i = 0; i < FLAG.length; i++)
		{
			dp[1][FLAG[i]] = Math.min(dp[1][FLAG[i]], i);
		}
		
		// 배열 채우기
		for (int n = 2; n < dp.length; n++)
		{
			for (int i = 2; i < 8; i++)
			{
				int start = (n - 1) * 2;
				int end = (n - 1) * 7 + 1;
				
				for (int j = start; j < end; j++)
				{
					dp[n][i + j] = Math.min(dp[n][i + j], dp[n - 1][j] + (long) Math.pow(10, n - 1) * dp[1][i]);
				}
			}
		}
	}
	
	/**
	 * 알고리즘 동작 함수
	 *
	 * @return [long] 동일한 선분의 갯수를 가지는 숫자가 나오기까지 걸리는 시간
	 */
	private static long solve()
	{
		// 결과
		long result = (long) Math.pow(10, N);
		
		// 1의 자리 숫자만 비교
		for (int num = 0; num < 10; num++)
		{
			// 입력된 숫자의 1의 자리값
			int units = numbers[N - 1];
			
			// 1의 자리 숫자와 다른 숫자이면서 선분의 갯수는 동일할 경우
			if (FLAG[units] == FLAG[num] && units != num)
			{
				// num이 1의 자리 숫자보다 클 경우
				if (num > units)
				{
					result = Math.min(result, num - units);
				}
				
				// num이 1의 자리 숫자보다 작을 경우
				else
				{
					result = Math.min(result, (long) Math.pow(10, N) + num - units);
				}
			}
		}
		
		// 비교할 선분의 갯수 (1의 자리를 위에서 이미 비교했으므로 1의 자리에 해당하는 선분값을 초기값으로 지정)
		int count = FLAG[numbers[N - 1]];
		
		// (10^i)의 자리 숫자부터 하나씩 비교
		for (int i = 2; i < N + 1; i++)
		{
			// (10^i-1)의 자리까지만 표기한 수
			long digit = number % (long) Math.pow(10, i);
			
			// (10^i)의 자릿수 선분 갯수 누적
			count += FLAG[numbers[N - i]];
			
			// (10^i)의 자릿수에 0 ~ 9를 대입하여 비교
			for (int num = 0; num < 10; num++)
			{
				// 비교할 선분의 갯수와 현재 숫자의 선분의 갯수차가 양수일 경우
				if (count - FLAG[num] >= 0)
				{
					// (10^i-1)의 자릿수에 현재 숫자를 곱한 수
					long pows = (long) Math.pow(10, i - 1) * num;
					
					// i-1 자리에서 선분의 합이 (count - FLAG[num])이 되는 가장 작은 수
					long target = dp[i - 1][count - FLAG[num]];
					
					// pows와 target의 합이 digit과 다르며, 유효한 값을 가지는 메모이제이션 배열일 경우
					if (digit != pows + target && target != Long.MAX_VALUE)
					{
						long val = pows + target - digit;
						
						// 계산한 값이 음수일 경우
						if (val <= 0)
						{
							// 10^N 자리를 넘어가므로 한 주기를 돌아 다시 카운팅해야한다.
							val += (long) Math.pow(10, N);
						}
						
						result = Math.min(result, val);
					}
				}
			}
		}
		
		return result;
	}
}

소스는 위와 같다. putDP() 메소드는 DP배열을 전개하며, solve() 메소드는 알고리즘을 수행한다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private static void putDP()
{
	dp = new long[N + 1][(N * 7) + 1];
	
	// 전체 배열을 long의 최대값으로 초기화
	for (long[] arr : dp)
	{
		Arrays.fill(arr, Long.MAX_VALUE);
	}
	
	// 초기값 설정
	for (int i = 0; i < FLAG.length; i++)
	{
		dp[1][FLAG[i]] = Math.min(dp[1][FLAG[i]], i);
	}
	
	// 배열 채우기
	for (int n = 2; n < dp.length; n++)
	{
		for (int i = 2; i < 8; i++)
		{
			int start = (n - 1) * 2;
			int end = (n - 1) * 7 + 1;
			
			for (int j = start; j < end; j++)
			{
				dp[n][i + j] = Math.min(dp[n][i + j], dp[n - 1][j] + (long) Math.pow(10, n - 1) * dp[1][i]);
			}
		}
	}
}

DP배열은 위 코드와 같이 전개하며, Arrays.fill(arr, Long.MAX_VALUE)를 통해 long의 최대값으로 배열을 초기화한다.

이후 dp[1][FLAG[i]] = Math.min(dp[1][FLAG[i]], i) 구문을 통해 한 자릿수에서 해당 선분값을 가지는 가장 작은 값을 할당한다.

모든 숫자의 조합은 0, 1, 2, 4, 7, 8로 이루어지므로, 각 숫자를 조합하여 나올 수 있는 모든 경우의 수를 비교하여 선분합의 최소값을 DP배열에 기록한다.

0_XXX에서 _은 한 자릿수에서 나올 수 있는 수의 조합이며, XXX는 세 자릿수에서 나올 수 있는 수의 조합이다.

즉, $i$는 _, $j$는 XXX를 표현한 것이다.

예시로, $N = 3$일 경우 $2 \leq i \leq 7$, $4 \leq j \leq 14$가 된다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
private static long solve()
{
	// 결과
	long result = (long) Math.pow(10, N);
	
	// 1의 자리 숫자만 비교
	for (int num = 0; num < 10; num++)
	{
		// 입력된 숫자의 1의 자리값
		int units = numbers[N - 1];
		
		// 1의 자리 숫자와 다른 숫자이면서 선분의 갯수는 동일할 경우
		if (FLAG[units] == FLAG[num] && units != num)
		{
			// num이 1의 자리 숫자보다 클 경우
			if (num > units)
			{
				result = Math.min(result, num - units);
			}
			
			// num이 1의 자리 숫자보다 작을 경우
			else
			{
				result = Math.min(result, (long) Math.pow(10, N) + num - units);
			}
		}
	}
	
	// 비교할 선분의 갯수 (1의 자리를 위에서 이미 비교했으므로 1의 자리에 해당하는 선분값을 초기값으로 지정)
	int count = FLAG[numbers[N - 1]];
	
	// (10^n)의 자리 숫자부터 하나씩 비교
	for (int n = 2; n < N + 1; n++)
	{
		// (10^n-1)의 자리까지만 표기한 수
		long digit = number % (long) Math.pow(10, n);
		
		// (10^n)의 자릿수 선분 갯수 누적
		count += FLAG[numbers[N - n]];
		
		// (10^n)의 자릿수에 0 ~ 9를 대입하여 비교
		for (int num = 0; num < 10; num++)
		{
			// 비교할 선분의 갯수와 현재 숫자의 선분의 갯수차가 양수일 경우
			if (count - FLAG[num] >= (n - 1) * 2)
			{
				// (10^n-1)의 자릿수에 현재 숫자를 곱한 수
				long pows = (long) Math.pow(10, n - 1) * num;
				
				// n-1 자리에서 선분의 합이 (count - FLAG[num])이 되는 가장 작은 수
				long target = dp[n - 1][count - FLAG[num]];
				
				// pows와 target의 합이 digit과 다르며, 유효한 값을 가지는 메모이제이션 배열일 경우
				if (digit != pows + target && target != Long.MAX_VALUE)
				{
					long val = pows + target - digit;
					
					// 계산한 값이 음수일 경우
					if (val <= 0)
					{
						// 10^N 자리를 넘어가므로 한 주기를 돌아 다시 카운팅해야한다.
						val += (long) Math.pow(10, N);
					}
					
					result = Math.min(result, val);
				}
			}
		}
	}
	
	return result;
}

실제 알고리즘을 수행하는 소스는 위와 같다.

long result = (long) Math.pow(10, N)은 알고리즘의 최대값으로 초기화하는 작업이다. 예를 들어, 384와 동일한 선분합을 가지는 수가 나올 시간을 찾는다고 해보자.

운 나쁘게 동일한 선분합을 가지는 수가 없다면 384부터 1씩 증가하여 한 사이클을 돌아 다시 384로 돌아올 것이다.

즉, 한 사이클 $c$의 값은 $c = 10^{N + 1}$으로 표현할 수 있다. 알고리즘의 결과는 이 값을 넘지 않는다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 1의 자리 숫자만 비교
for (int num = 0; num < 10; num++)
{
	// 입력된 숫자의 1의 자리값
	int units = numbers[N - 1];
	
	// 1의 자리 숫자와 다른 숫자이면서 선분의 갯수는 동일할 경우
	if (FLAG[units] == FLAG[num] && units != num)
	{
		// num이 1의 자리 숫자보다 클 경우
		if (num > units)
		{
			result = Math.min(result, num - units);
		}
		
		// num이 1의 자리 숫자보다 작을 경우
		else
		{
			result = Math.min(result, (long) Math.pow(10, N) + num - units);
		}
	}
}

초기값을 지정하기 위해 1의 자리 숫자를 비교하는 작업이다. 위 예제에서의 059_ 과정에 해당한다.

• 1의 자리보다 클 경우

  비교하는 숫자가 나오기까지의 시간을 구하여 result와 비교한다. 더 작은 값이 result가 된다.

• 1의 자리보다 작을 경우

  한 사이클을 돌고 난 뒤에 도달하는 수이므로, 최대 사이클 $c$에서 비교하는 숫자가 나오는데 걸리는 시간을 뺀다. 이를 result와 비교하여, 더 작은 값이 result가 된다.

비교할 선분합 count를 누적한다. 0598이라는 수가 있을 때, 059_에서 _는 8의 선분합인 7과 동일해야한다.

만약 05_X에서 _와 X는 9와 8의 선분합인 12와 동일해야할 것이다. 이러한 선분합을 저장하는 변수가 count다.

초기값으로 1의 자릿수가 가진 선분합인 FLAG[numbers[N - 1]]를 할당한다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// (10^n)의 자리 숫자부터 하나씩 비교
for (int n = 2; n < N + 1; n++)
{
	// (10^n-1)의 자리까지만 표기한 수
	long digit = number % (long) Math.pow(10, n);
	
	// (10^n)의 자릿수 선분 갯수 누적
	count += FLAG[numbers[N - n]];
	
	// (10^n)의 자릿수에 0 ~ 9를 대입하여 비교
	for (int num = 0; num < 10; num++)
	{
		// 비교할 선분의 갯수와 현재 숫자의 선분의 갯수차가 양수일 경우
		if (count - FLAG[num] >= (n - 1) * 2)
		{
			// (10^n-1)의 자릿수에 현재 숫자를 곱한 수
			long pows = (long) Math.pow(10, n - 1) * num;
			
			// n-1 자리에서 선분의 합이 (count - FLAG[num])이 되는 가장 작은 수
			long target = dp[n - 1][count - FLAG[num]];
			
			// pows와 target의 합이 digit과 다르며, 유효한 값을 가지는 메모이제이션 배열일 경우
			if (digit != pows + target && target != Long.MAX_VALUE)
			{
				long val = pows + target - digit;
				
				// 계산한 값이 음수일 경우
				if (val <= 0)
				{
					// 10^N 자리를 넘어가므로 한 주기를 돌아 다시 카운팅해야한다.
					val += (long) Math.pow(10, N);
				}
				
				result = Math.min(result, val);
			}
		}
	}
}

10의 자리 이상부터는 위 소스에 의해 구분된다.

digit는 $10^{N - 1}$의 자리에 해당하는 수가 할당된다. 05_X에서 X 부분이다.

count에 $10^N$의 선분의 합을 누적한다. count는 05_X에서 _X에 대한 선분 총합을 가지게 된다.

_에 0 ~ 9까지 대입되는 값을 num이라 한다. X에 대입되는 값은 DP배열에 이미 최적값을 계산해뒀으므로 그냥 꺼내서 쓰기만 하면 된다. 두 값이 count와 일치하면 된다.

여기에선 count에서 num을 뺀다. 그럼 나머지 숫자가 있을텐데, 이를 현재 자릿수에 해당하는 DP배열에서 꺼내 사용한다.

05_X에서 _X의 선분합은 12다. _에 3을 할당했을 경우 X는 dp[1][7]에 해당하는 숫자가 된다. 즉, 0598과 0538의 선분합은 같다.

조건문 if (count - FLAG[num] >= (n - 1) * 2)을 통해 X가 가져야할 선분합을 계산한다.

(n - 1) * 2인 이유는 $n = 1$일 경우 선분합의 범위는 $2 ~ 7$이기 때문, $n$에 비례하며, 일반식은 $(n - 1) * 2$와 같다. 이 최소값보다 커야 의미가 있다.

• pows $10^{N - 1}$에 해당하는 수
• target $10^{N - 1}$의 자리에서 count - FLAG[num]의 선분합을 갖는 DP배열값

원본값인 digit과 pows + target이 일치하지 않는 서로 다른 수이며, target이 DP배열의 초기값이 아닌 유효한 값을 가질 경우 이를 비교한다.

val은 pows + target과 digit 사이의 시간차다. 이 값이 음수일 경우는 한 사이클이 돌아가므로 사이클 값인 $c$를 더해 보정한다.

이후 마지막으로 계산된 result와 val을 비교하여 더 작은 값이 result가 된다.

여담

---

푼 건 7월 초에 풀었는데, 글 쓰는 와중 블로그 개편 작업을 시작하는 바람에 한 동안 못 하다가 이제서야 적는 풀이다.

한달 넘게 지나서 가물가물한데, 이 문제도 이해하는 데 일주일 정도 들었던 것 같다.

블로그 개편도 어느정도 마무리하고 안정화됐겠다, 다시 백준 알고리즘 풀이를 찬찬히 진행할 생각이다.

분류

---

• 다이나믹 프로그래밍