문제
11의 배수 판별법을 시뮬레이션한다. 큰 수가 주어졌을 때, 다음 규칙을 적용한다: 수의 마지막 자리를 떼어내고, 나머지 수에서 그 자리를 뺀다. 이 과정을 수가 2자리 이하가 될 때까지 반복하면서 각 단계의 수를 출력한다. 최종 2자리 이하의 수가 11의 배수이면 원래 수도 11의 배수이다.
입력
첫째 줄에 테스트 케이스 수 T가 주어진다. 각 테스트 케이스마다 큰 양의 정수가 한 줄에 주어진다.
출력
각 테스트 케이스마다 단계별 수를 출력하고, 마지막에 원래 수가 11로 나누어지는지 여부를 출력한다. 테스트 케이스 사이에 빈 줄을 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 121 | 121 11 The number 121 is divisible by 11. |
풀이
문자열로 큰 수를 처리하며 11 배수 판별 알고리즘을 단계별로 시뮬레이션한다.
- 테스트 케이스 수
T를 읽는다. - 수를 문자열로 읽어 원본
cur에 저장한다. - 문자열 길이가 2보다 클 동안 반복한다.
- 현재 문자열을 출력한다.
- 마지막 자리
val을 추출하고pop_back()으로 제거한다. - 나머지 문자열에서
val을 빌림 처리로 뺀다. - 앞자리가 0이 되면 제거한다.
- 최종 문자열을 출력하고,
stoi(s) % 11로 11 배수 여부를 판정한다. - 테스트 케이스 후 빈 줄을 출력한다.
핵심 아이디어: 11의 배수 판별을 큰 수에 대해 직접 문자열 뺄셈으로 구현한다. 마지막 자리를 빼는 연산이 11 배수 판별의 수학적 근거인 10 ≡ -1 (mod 11) 성질을 이용한 것이다. 빌림(borrow) 처리를 오른쪽에서 왼쪽으로 전파한다.
코드
#include <iostream>
#include <string>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
string s, cur; cin >> s;
cur = s;
while (s.length() > 2) {
cout << s << '\n';
int val = s.back() - '0',p,borrow, c;
s.pop_back();
p = s.length() - 1;
borrow = val;
while (borrow && p >= 0) {
c = s[p] - '0';
if (c >= borrow) {
s[p] = (c - borrow) + '0';
borrow = 0;
}
else {
s[p] = (c + 10 - borrow) + '0';
borrow = 1;
p--;
}
}
if (s[0] == '0') s = s.substr(1);
}
cout << s << '\n' << "The number " << cur << " is ";
if (stoi(s) % 11) cout << "not ";
cout << "divisible by 11.\n\n";
}
}복잡도
- 시간: O(D^2) — D자리 수에 대해 단계마다 최대 D번 빌림 처리
- 공간: O(D) — 문자열로 수를 저장