Problem F 풀이 (C++)

문제 링크 : https://codeforces.com/contest/1538/problem/F

숫자 l에서 1을 계속 더하여 r이 될 때까지 모든 자리수의 값의 변화 횟수를 구해야 한다.

그렇다면 결국 숫자 r의 자리수까지의 변화를 구해야 하는 것이 된다.

숫자 0에서 하나씩 더해보면,

1의 자리는 +1마다 바뀌고

10의 자리는 +10마다 바뀌고

10^n 자리는 + 10^n마다 바뀐다.

이 방식을 이용해 보면 일단 1의 자리는 r - l 번 더하므로 r - l 번 바뀐다고 생각할 수 있다.

그렇다면 다른 자리수는 위에서 계산한 것과 같이 r - l / 10^n 번 바뀔 것 같다고 생각이 들지만

주어지는 수 l은 0이 아니다. 그러므로 계산할 때 숫자 l을 계산하는 자리수 밑의 자리의 값들을 모두 0으로 만드는 방식을 사용한다.

예를 들면 l = 12, r = 200 이라면,

r - l = 188이다. 1의 자리는 188번 바뀌게 된다.

그리고 10의 자리를 계산할 때 숫자 l의 1의 자리를 보면 값이 2이다.

그렇다면 2에서 8만 더해주어도 10의 자리가 바뀐다.

그렇기 때문에 이때 우리는 10의 자리의 변하는 횟수를 계산하기 위해

그 아래의 모든 자리 수 값을 0으로 만들어 주려는 것이고 이를 위해

10 - 2 = 8 값을 숫자 l에 더한다.

그럼 l = 20이 되고 r - l은 180이 된다. 이때 10의 자리가 한번 바뀐다.

하지만 이후에는 위에서 계산한 것처럼 +10 할 때마다 l의 10의 자리가 바뀌는 것이기 때문에

이 상태로 만든 후 r - l / 10 + (방금 이 상태를 만들면서 한번 바뀐 횟수 1) 이 10의 자리가 바뀐 횟수가 된다.

100의 자리가 바뀐 횟수를 구한다면 마찬가지로 100 - l의 10의 자리까지의 수를 숫자 l에 더함으로써 상태를 바꾼 후 계산한다.

이런 방식으로 모든 자리수가 변경된 횟수를 구하고 모두 더하면 답이 된다.

이때 주의사항은 계산하고자 하는 자리부터 가장 위 자리까지의 숫자가 r과 l이 모두 같은 경우에는 계산하려는 자리수의 값이 변하지 않는다는 것을 의미하고 위의 계산과 같이 l에 값을 더했을 때 r보다 커지게 된다. 즉, r - l이 0보다 작아지게 된다. 때문에 위 계산 후의 r - l 값이 0 이상일 경우에만 값을 더하도록 조건을 설정한다.

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

#include <iostream> #include <vector>   using namespace std;   int main() {       int t;     cin >> t;          while (t--) {           int l, r;         cin >> l >> r;           long long answer = 0;         vector<pair<int, int>> v;                  int tenn = 10;           while (r / tenn != 0) {             v.push_back({ tenn - l % tenn, tenn });             tenn *= 10;         }           answer += r - l;           for (int i = 0; i < v.size(); i++)             if (r - l - v[i].first >= 0)                 answer += (r - l - v[i].first) / v[i].second + 1;              cout << answer << endl;     }       return 0; } Colored by Color Scripter

cs