🔗 Full Problem 1020

Jimin has an $N$-digit digital counter whose number increases by one every second. The number shown on the counter wraps around — once it reaches $10^{N - 1}$, it starts again from 0.

Each digit is made up of the following 7 segments.

INPUT
    +   +---+   +---+   +   +   +---+
    |       |       |   |   |   |
    +   +---+   +---+   +---+   +---+
    |   |           |       |       |
    +   +---+   +---+       +   +---+

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

Every two adjacent segments are connected by $+$. For example, 1 is made up of two segments, and 9 is made up of five segments.

Given the number currently shown on the counter, write a program to find the minimum number of seconds that must pass before a number with the same total number of segments as the currently displayed number appears.

The digits 1, 2, ..., 9, and 0 are made up of 2, 5, 5, 4, 5, 6, 3, 7, 5, and 6 segments respectively, and since every number must fill exactly $N$ digits, numbers shorter than $N$ digits may have leading zeros.

On the first line, the number currently shown on the counter is given. $N$ is equal to the length of that number (the number may start with 0). $N$ is a natural number less than or equal to 15.

On the first line, output the minimum number of seconds that must pass before the number shown on the counter has the same number of segments as it currently does.

INPUT
007

OUTPUT
11

The problem itself isn't too hard to understand. Think of a digital calculator display.

Multiple segments are needed to represent a digit, and it's easier to understand by looking at the diagram above rather than the symbols given in the problem statement. The number of segments needed to represent each digit is summarized in the table below.

For an arbitrary number 02, the number of segments needed to represent each digit is 6 and 5 respectively, requiring a total of 11 segments.

The number changes every second, so we just need to calculate how many seconds later a number with a total segment count of 11 appears. The closest number with a total segment count of 11 is 03, which takes 1 second.

If it exceeds the maximum value for the given number of digits, it wraps back around to 0 and starts counting again. In other words, for 02, since it's a two-digit number, once it passes 99, it wraps back around to 00.

Now let's consider the case of an arbitrary number 98. Since the given number has two digits, we know $N = 2$. The number of segments needed to represent 98 is 7 and 5 respectively, requiring a total of 12 segments.

99 also has a total of 10 segments, so it isn't the answer, and since the maximum value for a two-digit number is 99, it wraps around to 00 to find the value. This is the same concept as overflow.

0 is made up of 6 segments, so the number of segments needed to represent 00 is 12. In other words, the answer is 2 seconds.

Cases like this, where the number exceeds the given number of digits, must also be accounted for in the calculation.

The problem's requirements are intuitive, and its characteristics aren't too complex either. It's simply that the logic the problem demands is, on its own, difficult.

Since the number of digits can be as large as 15 (up to a hundred trillion), dynamic programming is well suited to quickly processing this large amount of data.

Also, since int can only handle values up to about 2.1 billion, we can infer that we need to use long data instead.

If you approach this brute-force, without any special consideration, it wouldn't be too difficult. You could split the number into individual digits, calculate and sum the segment counts, and then repeat this calculation while incrementing the current number by 1 each time. Of course, if it were that easy, I wouldn't have spent over a week puzzling over it.

Dynamic programming is more of a concept than a specific pattern-based technique like bipartite matching, so you need to derive an approach (such as a recurrence relation) that lets you apply it appropriately.

The core of this algorithm is the sum of segments. The number of segments needed to display a single digit ranges from 2 to 7. Since multiple digits can share the same segment count, there's some overlap.

If we list out the possible segment sums achievable from a single digit, and for each sum, note the smallest digit that can produce it, we get the following.

For example, there are 4 digits with a segment count of 5: [ 2, 3, 5, 9 ]. The smallest of these is 4... wait, let me restate: among these, the smallest is 2, so 2 is matched to the segment count of 5 in the table above.

The table above shows the possible cases for a single digit. If we map out the table for two digits, it looks as follows. Since the minimum for a single digit is 2 and the maximum is 7, we can infer that the range for two digits would span from 4 to 14.

This is how it can be expressed. You can immediately see that among two-digit numbers with a segment sum of 11, the smallest is 02.

Using this principle, we can expand the number of digits one at a time and quickly find values with the same segment sum.

For example, let's find the closest number to 0598 with the same segment sum. The segment sum of 0598 is 6 + 5 + 5 + 7 =

23

. In other words, we just need to find the number closest to 0598 whose segment sum is 23.

1. Comparing the ones digit

If we leave the ones digit blank, it can be written as 059_. Since 8's segment value is 7, we substitute 0 through 9 in sequence into _ to find a digit whose segment value equals 7. Note that the original value, 8, is excluded from the search.

Since the only single digit with a segment sum of 7 is 8 itself, there's no digit at the ones place with the same segment sum other than itself.

Therefore, no satisfying number can be found using the ones-digit combination alone.

2. Comparing the tens digit

If we leave the tens digit blank, it can be written as 05_X. _ is the position where 0 through 9 will be substituted, and X is filled in with the smallest digit that has the corresponding segment sum for that position.

In other words, X can only be one of 0, 1, 2, 4, 7, 8, based on the table above.

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

The sum of _ and X needs to equal the segment sum of 8 and 9 combined. So we need to find a combination with a segment sum of 12.

The candidates are 0500, 0528, 0538, 0558, 0560, 0582, and 0598.

However, 0598 is excluded since it's the original number itself, and while all the remaining numbers satisfy the condition, they are all smaller than 0598. Since these would only be reached after wrapping around a full cycle, it's too early to conclude anything yet.

3. Comparing the hundreds digit

If we leave the hundreds digit blank, it can be written as 0_XX.

In other words, XX can only be one of 00, 01, 02, 04, 07, 08, 11, 12, 14, 17, 88, based on the table above.

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

By substituting values into _ and XX, we find the number with a segment sum of 17, matching the segment sum of 5, 8, and 9 combined.

The candidates are 0002, 0200, 0300, 0408, 0500, 0602, 0788, 0804, and 0900.

Among these, 0602 differs from the input value, 0598, by 4, making it the closest number with the same segment count.

The answer this algorithm requires is the amount of time until the closest number with the same segment count appears. Since each digit changes once per second, the time it takes to go from 0598 to 0602 — 4 — is the answer.

In the example above, you could easily solve it by computing the segment sum of 0598, then calculating one by one starting from 0599 and moving forward. However, this approach is highly inefficient, so it doesn't fit the intent of the algorithm.

Below is a summary of the numbers with the minimum segment sum achievable for one-digit and two-digit numbers.

• One digit

• Two digits

If we compute the values in the table above and consolidate them into a single table, we can apply memoization.

Suppose we have an array dp[i][j] to which memoization will be applied. Each index has the following meaning.

• $i$: number of digits $(i = 1, 2, \, \, \, \dotsm \, \, \, , 14, 15)$
• $j$: the segment sum

※ i and j never equal 0. The reason is explained below.

• $dp[1][6]$: the smallest one-digit number with a segment sum of 6
• $dp[2][12]$: the smallest two-digit number with a segment sum of 12
• $dp[n][m]$: the smallest n-digit number with a segment sum of m

For example, computing $dp[3][6]$ gives the minimum three-digit number with a segment sum of 6, which would be 111 (2 + 2 + 2). We need to derive an expression for the array dp that produces the appropriate value like this.

An example of the DP array is shown below.

The DP array computed for up to three digits looks like above. The $i$ value grows in proportion to the number of digits. However, the array values themselves are fixed — the DP array's values don't change just because a different number was given as input.

To put it simply, given inputs of 0598 and 135, dp[2][7] is 12 in both cases.

Since $N$ represents the number of digits in the algorithm, the size of dp can be expressed as follows.

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

Arrays.fill(arr, Long.MAX_VALUE);

Since the element values can be large, we declare it as a long array. Array dp should be initialized with as large a value as reasonably possible.

In this document, the entire array is initialized to Long.MAX_VALUE, the maximum value for long.

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

The segment count for each digit is also encoded. FLAG returns the segment sum for the digit corresponding to each index.

FLAG[2] is the segment sum of the digit 2, and returns 5.

If $N = 3$, we have a three-digit number, and the maximum possible segment sum is 21. You might think this could be declared as an array with new long[3][21], but this leads to confusion due to the nature of computer languages.

Most computer languages treat array indices as starting from 0. If we declare the array this way, to look up the value for a two-digit number with a segment sum of 10, we'd need to call dp[1][9] instead of dp[2][10].

Particularly in a problem this complex, using variables like this can lead to a lot of confusion, so it's important to keep things aligned as much as possible. To handle this, we avoid using index 0 entirely, and instead add 1 to each declared size to widen the range, with the starting index treated as 1.

In other words, for this problem, any array entry where $i$ or $j$ equals 0 is never used, and carries no meaning whatsoever.

Dynamic programming skips the complex process of recalculating everything from scratch, and instead performs additional calculations building on previously computed results.

At the start, the calculation follows the standard logic, but afterward, the computed values are accumulated and used to calculate the next value. In particular, the larger the amount of data, the greater the speed advantage this provides.

So for dynamic programming, setting the initial values correctly is also very important. Here, the initial values can be defined as the possible segment-sum combinations achievable from a single digit.

Just enter the values from the table above into array dp. Since it's a single digit, $i = 1$ is fixed, and $j$ is the segment sum. The value is the digit itself.

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

Just declare it as shown above.

If you're not a fan of hardcoding this, there's also a way to write it like below.

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

This iterates through the FLAG array in order starting from 0, and assigns the smallest value with the corresponding segment value as the initial value.

Based on the initial values we've set, we expand the values in array dp. A single digit takes on a value between 2 and 7.

So then, since two digits are a combination of two single digits, they'll take on a value between 4 and 14.

In other words, the valid range for the DP array per number of digits is as follows.

$$\text{range for n digits} = (n - 1) * 2 \,\,\, \sim \,\,\, (n - 1) * 7$$

We only need to worry about this range for each number of digits.

There are six possible digits that can be assigned for a single digit: 0, 1, 2, 4, 7, 8. Two-digit numbers are also composed entirely of combinations of these digits.

So we combine 00, 01, 02, ~ 84, 87, 88 and assign the smallest number with a matching segment sum to dp.

For example, for dp[2][8], combinations like 01, 10, 44, and so on are possible. The smallest of these is 01, so dp[2][8] = 1.

JAVA
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]);
		}
	}
}

Expressed this way in code, it looks as above.

• $n$: number of digits
• $i$: the segment sum of the digit assigned to the $n$th position
• $j$: the segment sum of the digits assigned to the remaining positions

$n$ represents the number of digits, and since the ones digit has already been computed, it starts from 2.

start and end express the range for the $n$th digit position in code.

$i$ and $j$ each represent a segment sum — in the 0_XX example above, think of $i$ as the segment sum of _, and $j$ as the segment sum of XX.

We assign the smaller of dp[n][i + j] and Math.pow(10, n - 1) * dp[1][i] + dp[n - 1][j] to the dp array.

Repeating this until the array is complete gives us the finished DP array.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * Baekjoon Problem 1020 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/08/24/a1020">1020 Solution</a>
 * @since 2021.07.06 11:36:34
 */
public class Main
{
	// Segment count for each digit
	private static final int[] FLAG = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 5 };
	
	// Memoization array
	private static long[][] dp;
	
	// Input number
	private static long number;
	
	// Array of digits split by position
	private static int[] numbers;
	
	// Number of digits
	private static int N;
	
	/**
	 * Main function
	 *
	 * @param args: [String[]] parameters
	 *
	 * @throws IOException I/O exception
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// Input value
		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 array-filling function
	 */
	private static void putDP()
	{
		dp = new long[N + 1][(N * 7) + 1];
		
		// Initialize the entire array to the maximum value of long
		for (long[] arr : dp)
		{
			Arrays.fill(arr, Long.MAX_VALUE);
		}
		
		// Set initial values
		for (int i = 0; i < FLAG.length; i++)
		{
			dp[1][FLAG[i]] = Math.min(dp[1][FLAG[i]], i);
		}
		
		// Fill the array
		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]);
				}
			}
		}
	}
	
	/**
	 * Algorithm execution function
	 *
	 * @return [long] the time until a number with the same segment count appears
	 */
	private static long solve()
	{
		// Result
		long result = (long) Math.pow(10, N);
		
		// Compare only the ones digit
		for (int num = 0; num < 10; num++)
		{
			// The ones digit value of the input number
			int units = numbers[N - 1];
			
			// If it's a different digit from the ones digit but has the same segment count
			if (FLAG[units] == FLAG[num] && units != num)
			{
				// If num is greater than the ones digit
				if (num > units)
				{
					result = Math.min(result, num - units);
				}
				
				// If num is less than the ones digit
				else
				{
					result = Math.min(result, (long) Math.pow(10, N) + num - units);
				}
			}
		}
		
		// The segment count to compare against (since the ones digit was already compared above, initialize with the ones digit's segment value)
		int count = FLAG[numbers[N - 1]];
		
		// Compare digit by digit starting from the (10^i) position
		for (int i = 2; i < N + 1; i++)
		{
			// The number expressed only up to the (10^i-1) position
			long digit = number % (long) Math.pow(10, i);
			
			// Accumulate the segment count for the (10^i) position
			count += FLAG[numbers[N - i]];
			
			// Compare by substituting 0 ~ 9 into the (10^i) position
			for (int num = 0; num < 10; num++)
			{
				// If the difference between the segment count to compare and the current digit's segment count is non-negative
				if (count - FLAG[num] >= 0)
				{
					// The value obtained by multiplying the current digit by the (10^i-1) position
					long pows = (long) Math.pow(10, i - 1) * num;
					
					// The smallest value at position i-1 whose segment sum is (count - FLAG[num])
					long target = dp[i - 1][count - FLAG[num]];
					
					// If the sum of pows and target differs from digit, and the memoization array holds a valid value
					if (digit != pows + target && target != Long.MAX_VALUE)
					{
						long val = pows + target - digit;
						
						// If the computed value is negative
						if (val <= 0)
						{
							// It exceeds the 10^N position, so we need to wrap around a full cycle and count again
							val += (long) Math.pow(10, N);
						}
						
						result = Math.min(result, val);
					}
				}
			}
		}
		
		return result;
	}
}

The source is as shown above. The putDP() method expands the DP array, and the solve() method carries out the algorithm.

JAVA
private static void putDP()
{
	dp = new long[N + 1][(N * 7) + 1];
	
	// Initialize the entire array to the maximum value of long
	for (long[] arr : dp)
	{
		Arrays.fill(arr, Long.MAX_VALUE);
	}
	
	// Set initial values
	for (int i = 0; i < FLAG.length; i++)
	{
		dp[1][FLAG[i]] = Math.min(dp[1][FLAG[i]], i);
	}
	
	// Fill the array
	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]);
			}
		}
	}
}

The DP array is expanded as shown in the code above, and Arrays.fill(arr, Long.MAX_VALUE) initializes the array to the maximum value of long.

Then, through the statement dp[1][FLAG[i]] = Math.min(dp[1][FLAG[i]], i), the smallest single-digit value with the corresponding segment value is assigned.

Since every combination of digits consists of 0, 1, 2, 4, 7, 8, we compare every possible combination formed from these digits, and record the minimum segment sum values into the DP array.

In 0_XXX, _ represents the possible single-digit combinations, and XXX represents the possible three-digit combinations.

In other words, $i$ represents _, and $j$ represents XXX.

For example, if $N = 3$, then $2 \leq i \leq 7$ and $4 \leq j \leq 14$.

JAVA
private static long solve()
{
	// Result
	long result = (long) Math.pow(10, N);
	
	// Compare only the ones digit
	for (int num = 0; num < 10; num++)
	{
		// The ones digit value of the input number
		int units = numbers[N - 1];
		
		// If it's a different digit from the ones digit but has the same segment count
		if (FLAG[units] == FLAG[num] && units != num)
		{
			// If num is greater than the ones digit
			if (num > units)
			{
				result = Math.min(result, num - units);
			}
			
			// If num is less than the ones digit
			else
			{
				result = Math.min(result, (long) Math.pow(10, N) + num - units);
			}
		}
	}
	
	// The segment count to compare against (since the ones digit was already compared above, initialize with the ones digit's segment value)
	int count = FLAG[numbers[N - 1]];
	
	// Compare digit by digit starting from the (10^n) position
	for (int n = 2; n < N + 1; n++)
	{
		// The number expressed only up to the (10^n-1) position
		long digit = number % (long) Math.pow(10, n);
		
		// Accumulate the segment count for the (10^n) position
		count += FLAG[numbers[N - n]];
		
		// Compare by substituting 0 ~ 9 into the (10^n) position
		for (int num = 0; num < 10; num++)
		{
			// If the difference between the segment count to compare and the current digit's segment count is non-negative
			if (count - FLAG[num] >= (n - 1) * 2)
			{
				// The value obtained by multiplying the current digit by the (10^n-1) position
				long pows = (long) Math.pow(10, n - 1) * num;
				
				// The smallest value at position n-1 whose segment sum is (count - FLAG[num])
				long target = dp[n - 1][count - FLAG[num]];
				
				// If the sum of pows and target differs from digit, and the memoization array holds a valid value
				if (digit != pows + target && target != Long.MAX_VALUE)
				{
					long val = pows + target - digit;
					
					// If the computed value is negative
					if (val <= 0)
					{
						// It exceeds the 10^N position, so we need to wrap around a full cycle and count again
						val += (long) Math.pow(10, N);
					}
					
					result = Math.min(result, val);
				}
			}
		}
	}
	
	return result;
}

The source that actually carries out the algorithm is as shown above.

long result = (long) Math.pow(10, N) initializes the value to the algorithm's maximum possible value. For example, let's say we're finding the time until a number with the same segment sum as 384 appears.

If, unluckily, there's no other number with the same segment sum, incrementing by 1 from 384 would wrap around a full cycle and eventually come back to 384 again.

In other words, the value of one full cycle $c$ can be expressed as $c = 10^{N + 1}$. The algorithm's result never exceeds this value.

JAVA
// Compare only the ones digit
for (int num = 0; num < 10; num++)
{
	// The ones digit value of the input number
	int units = numbers[N - 1];
	
	// If it's a different digit from the ones digit but has the same segment count
	if (FLAG[units] == FLAG[num] && units != num)
	{
		// If num is greater than the ones digit
		if (num > units)
		{
			result = Math.min(result, num - units);
		}
		
		// If num is less than the ones digit
		else
		{
			result = Math.min(result, (long) Math.pow(10, N) + num - units);
		}
	}
}

This is the process of comparing the ones digit to determine the initial value. It corresponds to the 059_ process from the example above.

• If greater than the ones digit

  Compute the time until the compared digit appears, and compare it against result. The smaller value becomes result.

• If less than the ones digit

  Since this is a value reached only after a full cycle, we subtract the time it takes for the compared digit to appear from the maximum cycle $c$. Compare this against result, and the smaller value becomes result.

We accumulate the segment sum to compare against, count. For the number 0598, in 059_, _ must equal 7, the segment sum of 8.

For 05_X, _ and X combined must equal 12, the segment sum of 9 and 8. The variable that stores this segment sum is count.

We assign FLAG[numbers[N - 1]], the segment sum of the ones digit, as the initial value.

JAVA
// Compare digit by digit starting from the (10^n) position
for (int n = 2; n < N + 1; n++)
{
	// The number expressed only up to the (10^n-1) position
	long digit = number % (long) Math.pow(10, n);
	
	// Accumulate the segment count for the (10^n) position
	count += FLAG[numbers[N - n]];
	
	// Compare by substituting 0 ~ 9 into the (10^n) position
	for (int num = 0; num < 10; num++)
	{
		// If the difference between the segment count to compare and the current digit's segment count is non-negative
		if (count - FLAG[num] >= (n - 1) * 2)
		{
			// The value obtained by multiplying the current digit by the (10^n-1) position
			long pows = (long) Math.pow(10, n - 1) * num;
			
			// The smallest value at position n-1 whose segment sum is (count - FLAG[num])
			long target = dp[n - 1][count - FLAG[num]];
			
			// If the sum of pows and target differs from digit, and the memoization array holds a valid value
			if (digit != pows + target && target != Long.MAX_VALUE)
			{
				long val = pows + target - digit;
				
				// If the computed value is negative
				if (val <= 0)
				{
					// It exceeds the 10^N position, so we need to wrap around a full cycle and count again
					val += (long) Math.pow(10, N);
				}
				
				result = Math.min(result, val);
			}
		}
	}
}

From the tens digit onward, the logic is split off as shown in the source above.

digit is assigned the number corresponding to the $10^{N - 1}$ position. This is the X portion in 05_X.

count accumulates the segment sum for the $10^N$ position. count ends up holding the total segment sum for _X in 05_X.

Let num be the value substituted into _, ranging from 0 to 9. The value substituted into X has already had its optimal value computed in the DP array, so we just pull it out and use it. Together, the two values need to match count.

Here, we subtract num from count. What remains is the leftover segment sum, which we pull from the DP array corresponding to the current number of digits.

In 05_X, the segment sum of _X is 12. If _ is assigned 3, then X becomes the digit corresponding to dp[1][7]. In other words, 0598 and 0538 have the same segment sum.

The condition if (count - FLAG[num] >= (n - 1) * 2) computes the segment sum that X must have.

The reason for (n - 1) * 2 is that when $n = 1$, the range of the segment sum is $2 ~ 7$; scaling proportionally with $n$, the general formula becomes $(n - 1) * 2$. It's only meaningful if the value is greater than this minimum.

• pows the value corresponding to $10^{N - 1}$
• target the DP array value for the $10^{N - 1}$ position with a segment sum of count - FLAG[num]

We compare when the original value digit differs from pows + target, and when target holds a valid value rather than the DP array's initial value.

val is the time difference between pows + target and digit. If this value is negative, it means a full cycle has occurred, so we correct it by adding the cycle value $c$.

Finally, we compare the last computed result against val, and the smaller value becomes result.

I actually solved this in early July, but while writing up the solution, I started a blog redesign project and couldn't get back to it for a while — this write-up is only happening now, belatedly.

It's been over a month, so my memory of it is a bit hazy, but I recall this problem also took me about a week to fully understand.

Now that the blog redesign is mostly wrapped up and stabilized, I'm planning to steadily get back to working through Baekjoon algorithm problems again.

• Dynamic Programming