codeforces.com/contest/1409/problem/D
Problem - D - Codeforces
codeforces.com
이 문제는 숫자가 매번 증가하기만 할 뿐이라는 점에 착안해야 한다.
27이라는 숫자가 있을 때, 각 자리에 있는 숫자들은 2와 7이다. 그리고 그들의 합은 9. 지금부터 편의상 9를 27의 '숫자합'이라고 부르겠다.
7이라는 숫자가 있다고 한다면, 7에서 1을 증가시키면 8이 된다. 8은 7보다 숫자합이 크다. 8에서 또 1을 증가시키면 9가 되고. 9의 숫자합은 8의 그것보다 크다. 여기까지 보면, 숫자를 1씩 증가시키기 때문에 숫자합은 점점 커질 뿐이다. 하지만! 수가 길어질 때 (자릿수가 하나 더 생겼을 때) 드디어 숫자합은 작아질 수 있다. 방금 전 예시의 9에서 1을 증가시키면 이제 10이 되고 숫자합은 1이다. 앞 자릿수가 바뀔 때, 뒤따르는 모든 숫자가 0이 되기 때문에, 숫자합이 작아질 가능성이 생기는 것이다. 정리하면 아래의 사실을 이용해야 하는 것이다.
'앞 자릿수가 커질 때만 숫자합이 작아진다'
위의 예시를 보자. 132가 주어졌고, 4가 목푯값이다. 132의 숫자합은 6이다. 132에서 139까지는 계속 숫자가 증가하므로 숫자합이 4와 같거나 4보다 작아질 수 없다. 140이 되면 숫자합이 5가 되어 처음 시작한 6보다는 작아졌지만 아직도 4보다는 크다. 이제 140부터 199까지는 계속 답이 나오지 않는다. 200이 되면 숫자합이 2가 되어 드디어 4보다 작아지게 된다. 132에서 200까지는 68번의 moves가 필요한 것이므로 68이 정답이 된다.
이번엔 132와 1이 주어졌다고 하자. 앞서 보았던 예시에서와 같이, 200이 되면 숫자합이 2가 된다. 하지만 이마저도 1보다 크다. 이제 200부터 999까지는 전부 2보다 큰 값이므로 넘길 수 있다. 200부터 999까지 일일이 숫자합을 계속하면서 대조해보는 방식으로 풀이하면 당연히 시간 초과가 나게 된다. 이제 1000이 되면 숫자합이 1이 되어 답을 구할 수 있게 된다.
<주요 내용>
그리디, 각 자리 수의 합
가장 중요한 부분은 아래와 같다. i=10부터 시작하여 몫을 취하고 다시 i를 더하여 다음 자릿수로 바로 넘어가는 것이다.
n = n//i*i+i
<코드>
각 자리에 있는 숫자들을 합을 구하는 등의 연산은 자주 활용되므로, 정렬처럼 몇 가지 방법을 알아두는 게 좋다. 필자는 이 문제를 파이썬으로 풀어서 str함수를 통해 숫자를 통째로 문자열로 변환하고 하나씩 보면서 int화 하였는데, C++을 사용했다면 10으로 계속 나누어서 나머지를 취하는 식으로 각 자리에 있는 숫자를 구했을 것이다.
파이썬 AC 코드
import sys
import heapq
si = sys.stdin.readline
def digitSum(n):
n = str(n)
ret = 0
for e in n:
ret += int(e)
return ret
def main():
t = int(si())
while t:
t -= 1
n, s = [int(e) for e in si().split()]
if digitSum(n) < s:
print(0)
else:
i, temp = 10, n
while digitSum(n) > s:
n = n//i*i+i
i *= 10
print(n-temp)
if __name__ == '__main__':
main()