백준 1081 합

알고리즘 문제/math

gaelim 2019. 3. 9. 16:28

문제보기

L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오.

U은 0보다 크거나 같고, 2,000,000,000보다 작거나 같은 정수이고, L은 0보다 크거나 같고, U보다 작거나 같은 정수이다.

이 문제는 철저하게 수학 문제이다. 나는 접근방법을 보고나서야 풀 수 있었다.

접근법은 10단위로 생각할 것.

10 ~ 29 까지 1 단위 자리의 0~ 9 의 발견횟수는 각각 (2-1+1) 이다. 이를 기준으로 계산한다.

만약 Lower, Upper 구간이 0이 아니라고 해보자. 이 경우 0 으로 맞춰줘야한다.

- Lower, Upper 도 1씩 올리던,

- Lower, Upper 를 1씩 내리던,

- Lower 를 1씩 내리고, Upper를 1씩 올리던

- Lower 를 1씩 올리고, Upper를 1씩 내리던

해줘야할 것 인데 어떤게 맞을까?

Lower 를 1씩 올리고, Upper를 1씩 내려서 맞춰주자. 그래야 우리가 원하는 알고리즘이 수행된다.

Lower, Upper를 0으로 이동시키는 동안 그 Lower와 Upper가 가지고 있는 숫자들을 base=1씩 증가시켜준다.

그리고 (Lower/10 - Upper/10)*base 만큼 0~9를 증가시켜준다.

그리고 Lower, Upper의 자리수를 줄여준다. 이때, 자리수를 줄이는 것은 이 알고리즘에서 무엇을 뜻하냐면 base를 10 곱해주는 것이다.

알고리즘이 체크하는 자리수가 증가한 것이기 때문에 발견횟수가 10씩 곱해준것만큼 늘어난다고 생각해야한다.

예로, 10 ~ 19 에서 1자리수의 0~9 발견횟수는 base = 1이다.

100 에서 199 를 생각해보자. 1 자리수의 0 ~9 발견횟수는 (19 -10 +1) = 10 회이다.

그리고 자리수를 줄여주었을때 10 에서 19가 된다. 이때 1 자리수(사실은 10자리수)의 0~9 발견횟수는 10회이다. 왜냐하면 100 에서 199 사이의 수 110 과 119만 고려하자. 10의 자릿수에서 1의 발견횟수는 10회이다.

이것이 반복적으로 수행되면서 알고리즘은 Lower > Upper 가 되는 순간 끝이난다.

흥미로운 문제다.

swexpert