[platinum3][해설,알고리즘 분류 안봄] 1020 디지털 카운터

https://www.acmicpc.net/problem/1020

 

아이디어는 비교적 어렵지 않게 생각할 수 있지만 구현이 좀 까다로웠던 문제였다.

 

dp[현재까지의 자리수][총 사용한 선분의 개수] = 지금 자리수에서 사용한 선분으로 만들 수 있는 최소의 수

라고 생각해보자.

dp[n-1][0] ,  ...   dp[n-1][100] 까지 계산했다고 가정해보자

n번째 자리에서 0~9 까지의 수가 온다고 생각해본다.

 

총 k개를 사용할 거라고 할 때 n번째에서 숫자 0이 오게 된다면,

dp[n][k] =  0 * 10^n    +    dp[n - 1][k - 0의 선분수]

가 된다. 단, dp[n - 1][k - 0의 선분수] 가 존재할 때만 이다.

만약 이때 존재하지 않는다면 1로 넘어가서  dp[n - 1][k - 1의선분수]  가 존재하는지 찾아보고, 있다면

dp[n][k] = 1 * 10 ^ n + dp[n - 1][k - 1의 선분수] 가 된다.

존재한다면 이렇게 dp를 구하고 다음 수는 생각할 필요가 없다.(greedy한 방식)

 

숫자 N = 32543256843이 존재한다고 치면, 

N의 총 선분수를 구한다.

3의 총 선분수를 구한다. 5이다. 3다음의 수 4부터 9까지 선분수가 5인 경우가 있는지 찾는다.

없다면  숫자 43의 총 선분수를 구한다. 8이다.     4 다음의 수 5부터 dp[1][8(73의 선분수) - 5(5의선분수)] 가 존재하는지 찾는다. 존재한다면, 10의자리가 5일때  선분의 수가 총 73이 되게 만들 수 있는 것이다. 

ans = 5 * 10 + dp[1][3] - 43.

 

만약 5일때 존재하지 않으면 6,7,8,.... 을 찾아보고 이때도 없으면 100의 자리로 넘어가서 9 ,,, , 1000의 자리에서 7,8,9... 이렇게 찾아보면 된다. 만약 99999999999까지 없다면,,,

10 ^ (카운터의 총 자리수 + 1 ) - N 까지 시간이 지난뒤 카운터가 0이 되었을 때까지인 passedTime를 구한다.

 

여기에 ans = passedTime + dp[ 총 자리수][N의 총 선분수]