[BOJ] 31288 - 캬루

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

BOJ - 캬루

문제 유형: 수학, 애드 혹, 해 구성하기, 정수론

문제 난이도: Silver II

시간 제한: 1초

메모리 제한: 1024MB

 

문제

이번에 캬루는 소수를 배신했다. 소수의 한 자리를 바꾸어서 소수가 아니게 만들어버렸다. 구체적으로는, 0으로 시작하지 않는 N자리 소수 P에 대해 어떤 수 Q가 P-캬루라는 것은 다음을 모두 만족하는 것을 의미한다.

•  Q는 2 이상의 N자리 정수이며, 0으로 시작하지 않는다.
•  P와 Q의 서로 다른 자릿수는 하나뿐이다.
•  Q는 소수가 아니다.

다음은 N=2,P=19일 때 P-캬루와 P-캬루가 아닌 수의 예시이다.

•  Q=9는 1자리 정수이므로 19-캬루가 아니다. 09처럼 수가 0으로 시작할 수는 없다.
•  Q=92는 P=19와 서로 다른 자릿수가 두 개이므로 19-캬루가 아니다.
•  Q=29는 소수이기 때문에 19-캬루가 아니다.
•  Q=16,49 등은 19-캬루이다.

 N자리 소수 P가 주어졌을 때, P-캬루인 수가 적어도 N개 있다는 것을 증명할 수 있다. 이 N개의 수를 직접 찾아보자.

 

풀이

한 자리수씩 바꿔보면서 합성수인지 알아내면 된다.

너무 복잡하게 생각할 거 없이, 다음의 경우의 수만 고려해도 편해진다;

• 2의배수: 일의 자리가 짝수
• 5의 배수: 일의 자리가 5 (0인경우는 2의배수에서 이미 걸렀다고 가정하자..)
• 3의 배수: 모든 자릿수의 합이 3의 배수

2,5,3의 배수인지만 고려해도, N자리수에서 N개의 조건에 맞는 수를 생성하는 건 어려운 문제가 아니다.

단, N=1인경우 조심하자. 코드에서 볼 수 있듯이, 최고로 높은 자릿수를 조작하지 않는다. (맨앞에서 0오는것 방지, 그리고 이전에 보통 끝남)

그래서 이 때의 오류를 방지하기 위해, 특이 처리를 해주자. 4의 경우는 2의 배수이고, 1자리수인경우 항상 이 수를 찾을 수 있다.

 

count개 생성하고, 마친다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int isDividedBy253(string &karylNum, int n) {
  if ((karylNum[n - 1] - '0') % 2 == 0)
    return 2;
  if (karylNum[n - 1] == '5')
    return 5;

  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += karylNum[i] - '0';
  }

  if (sum % 3 == 0)
    return 3;
  return -1;
}

void solve(string num) {
  int n = num.size();
  if (n == 1) {
    cout << "4 2\n";
  }
  string karylNum(num);

  int count = 0;
  for (int digit = n - 1; digit > 0; --digit) {
    for (char newDigit = '0'; newDigit <= '9'; ++newDigit) {
      if (newDigit == num[digit])
        continue;
      karylNum[digit] = newDigit;

      int res = isDividedBy253(karylNum, n);
      if (res != -1) {
        cout << karylNum << " " << res << "\n";
        ++count;
        if (count >= n)
          return;
      }
    }
    karylNum[digit] = num[digit];
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  vector<string> nums(t);
  string temp;
  for (int i = 0; i < t; ++i) {
    cin >> temp;
    cin >> nums[i];
  }

  for (int i = 0; i < t; ++i) {
    solve(nums[i]);
  }
  return 0;
}