[Codeforces Round 1004(Div.2)] C. Devyatkino

https://codeforces.com/contest/2067/problem/C

Codeforces Round 1004(Div.2) - C. Devyatkino

문제 유형: 수학, 그리디, 탐색, 브루트 포스

시간 제한: 2초

메모리 제한: 256MB

 

문제

You are given a positive integer n. In one operation, you can add to n any positive integer whose decimal representation contains only the digit 9, possibly repeated several times.

What is the minimum number of operations needed to make the number n contain at least one digit 7 in its decimal representation?

For example, if n=80, it is sufficient to perform one operation: you can add 99 to n, after the operation n=179, which contains the digit 7.

 

양의정수 n이 주어진다.

한 번의 연산으로, 당신은 n에 99999....99를 더할 수 있다. 이를 여러 번이고 할 수 있다.

10진수 표현에서 7을 적어도 한 번이라도 표함하게 만들기 위해서 필요한 최소 연산의 수는 몇 번인가?

예를 들어, n=80이면, 99를 더했을 때, 179가 나온다. 이는 7을 포함한다.

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10^4). The description of the test cases follows.

The only line of each test case contains an integer n (10≤n≤10^9).

 

첫째 줄에 테스트케이스의 수 t가 주어진다.

각 테스트케이스의 첫째 줄에는 n이 주어진다.

 

출력

For each test case, output the minimum number of operations required for the number n to contain the digit 7.

7을 포함하도록 하는 최소의 연산 횟수를 구하시오.

 

풀이

Editorial: https://codeforces.com/blog/entry/139415?locale=en

우선, 연산의 횟수가 최대 9번임을 알 수 있다.

매 번의 연산마다 항상 일의자릿수가 다이얼(-1씩)되는데, 일의 자릿수는 10마다 사이클이 돌기 때문이다.

 

또한, 9999....99대신, 우리는 10^n-1을 여러 번 더하는 것으로 생각할 수 있다.

n이 어떻던, 연산을 k번 하면, 위에는 어떻게 되던(+10, +100000, +1000 등등..), -k는 항상 연산된다.

그리고, 그 위의 자릿수들은 최대 k가 증가된다. (ex. 9를 세번 더하면, 30을 더하고 3을 뺀것과 같다.)

즉, n-k에서 10의자릿수 이상은 각각 최대 k가 증가된 것이다.

즉, n-k에서 10의자릿수 이상부터 '7'이하인 최대 숫자를 찾는다. 이를 md라고 하자.

7-md가 k 이상이라면, k번 더한 것에서는 '7'이 적어도 한 번 나왔다는 뜻이다.

 

k >= 7-md인경우, k번연산 시 답이 나온다 했는데, k=7인 경우를 생각해보자.

md >= 0이므로, 항상 참이 된다.

즉, 7,8,9는 사실 탐색할 필요 없다. 최대 상한은 7회 연산이 된다.

 

또한, 위의 풀이를 보아서, 10^n-1을 더할 때, 어느 한 자릿수를 '7'로 만들겠다는 목표 하에, n의 값이 처음보다 더 작아지거나, 커질 이유가 없다.

즉, 9를 더하고, 99를 더할 이유가 없다는 것이다.

고로, 9, 99, 999, ... , 99999999인경우를 각각 최대 6번 더해보면서, 최소 연산횟수를 갱신하면 된다.

최대 상한이 7이니, 7에서 시작하면 된다.

처음 풀이를 v1, 이 두 번째 풀이를 v2로 했다.

v2는 v1을 떠올리고 난 뒤에 떠올리기 좋다고 한다.

 

코드

C++

 

v1

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;

  for (int i = 0; i <= 9; ++i) {
    string s = to_string(n - i);
    int md = 0;
    for (char ch : s) {
      if (ch <= '7') {
        md = max(md, ch - '0');
      }
    }
    if (i >= 7 - md) {
      cout << i << "\n";
      return;
    }
  }
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}

 

v2

#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<int> adds = {9, 99, 999, 9999, 99999, 999999, 9999999, 99999999};

bool contains_seven(ll x) {
  while (x > 0) {
    if (x % 10 == 7)
      return true;
    x /= 10;
  }
  return false;
}

void solve() {
  ll n;
  cin >> n;

  if (contains_seven(n)) {
    cout << "0\n";
    return;
  }

  int ans = 7;
  for (int i = 0; i < 8; ++i) {
    ll x = n;
    for (int j = 0; j < 6; ++j) {
      x += adds[i];
      if (contains_seven(x)) {
        ans = min(ans, j + 1);
        break;
      }
    }
  }

  cout << ans << "\n";
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();
}