매 단계마다 B로 나누어 떨어지도록 A에 N개의 자릿수 추가하기

문제 개요

a, b, n 세 값이 주어졌을 때, 다음 조건들을 고려하여 매 반복(iteration) 후 a가 b로 나누어 떨어지도록 a에 n개의 자릿수를 추가하는 최적의 해답을 찾아야 합니다.

조건

a에 자릿수를 추가한 결과가 b로 나누어 떨어지는 방식으로 추가해야 합니다.
위 과정을 n번 반복한 후, 만들 수 있는 가장 작은 a 값을 출력합니다.
연산이 불가능한 경우 "fail"을 출력합니다.

즉, 자릿수를 하나 추가할 때마다 그 결과가 b로 나누어 떨어지는지 반드시 확인해야 합니다.

입력 및 출력 예시

입력:

a=5 b=4 n=4

출력:

동작 원리

먼저 0부터 9 사이의 숫자를 a 뒤에 하나씩 붙여 보면서, a가 b로 나누어 떨어지는지 확인합니다. 만약 어떤 숫자를 붙여도 a가 b로 나누어 떨어지지 않는다면 정답은 -1, 즉 실패입니다. 이는 n개의 자릿수를 아무리 추가해도 a가 절대 b로 나누어 떨어지지 않는다는 의미입니다.

반대로 조건을 만족하는 숫자가 존재한다면, 그중 가장 작은 숫자를 먼저 추가합니다. 이후에는 0을 (n-1)번 추가하면 됩니다. 그 이유는 간단합니다. 어떤 수 a가 b로 나누어 떨어진다면, a×10, a×100처럼 뒤에 0을 붙인 수 역시 b로 나누어 떨어지기 때문입니다. 따라서 첫 자릿수만 신중하게 선택하면, 나머지 자릿수를 모두 0으로 채우는 것이 항상 가장 작은 값을 만드는 전략입니다.

C++ 구현 예시

#include <iostream>
using namespace std;
int main() {
   int a = 5, b = 4, n = 4;
   int num = a;
   // 0~9 중 a*10+i가 b로 나누어 떨어지는 첫 번째 숫자를 찾습니다.
   for (int i = 0; i <= 9; i++) {
      int temp = a * 10 + i;
      if (temp % b == 0) {
         a = temp;
         break;
      }
   }
   // 어떤 숫자도 조건을 만족하지 못하면 실패(-1) 처리
   if (num == a) {
      a = -1;
   }
   // 남은 (n-1)개의 자릿수를 0으로 채웁니다.
   for (int j = 0; j < n - 1; j++) {
      a *= 10;
   }
   if(a > -1) {
      cout << a;
   } else {
      cout << "fail";
   }
   return 0;
}

코드 설명

위 코드는 먼저 0부터 9까지의 숫자를 차례대로 시도하며 a×10+i가 b로 나누어 떨어지는지 검사합니다. 조건을 만족하는 숫자를 찾으면 즉시 a를 갱신하고 반복을 종료합니다. 만약 한 번도 갱신되지 않았다면(num == a), 실패를 의미하는 -1로 설정합니다. 이후 남은 (n-1)번의 반복에서 a에 10을 곱해 뒤에 0을 붙이고, 최종적으로 성공 여부에 따라 결과 또는 "fail"을 출력합니다.