이번에는 백준 4375번 1 문제를 풀어보았습니다.
이 문제는 각 자릿수가 모두 1로만 이루어진 수 중에서, 주어진 n의 배수가 되는 가장 작은 수의 자리수를 구하는 문제입니다.
처음에는 문자열을 직접 만들어서 수로 바꾸는 방식으로 접근했지만, 숫자가 너무 커질 수 있어서 결국 모듈러 연산을 중간중간 적용하는 방식으로 정리하게 되었습니다.
문제 설명
2와 5로 나누어 떨어지지 않는 정수 n이 주어졌을 때,
각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 구하면 됩니다.
예를 들어 어떤 n에 대해
1111111111
이런 식으로 수를 늘려가다가 n으로 나누어 떨어지는 순간의 길이를 출력하는 문제입니다.
입력은 여러 개의 테스트 케이스로 이루어져 있고, 파일 끝까지 반복해서 처리해야 합니다.
처음 생각한 방식
처음에는 "1" 문자열을 계속 뒤에 붙여가면서 수를 직접 만들고,
그 값을 정수로 바꿔서 % n을 확인하는 방식으로 구현했습니다.
즉,
"1""11""111"
이렇게 문자열을 늘려가고,
각 단계마다 atoll()로 숫자로 바꿔서 나누어 떨어지는지 확인하는 방식이었습니다.
실패한 코드
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
while (cin >> n) {
int cnt = 1;
string mod = "1";
while ((atoll((mod.c_str())) % n) != 0) {
cnt++;
mod += "1";
}
cout << cnt << endl;
}
return 0;
}왜 실패했는가
처음에는 int보다 큰 수가 될 수 있으니 long long을 쓰면 될 것이라고 생각했습니다.
하지만 이 문제는 1이 계속 붙으면서 숫자의 길이가 매우 길어질 수 있습니다.
즉, 111111111111...처럼 자릿수가 계속 늘어나기 때문에 long long조차 감당할 수 없는 크기가 됩니다.
결국 이 방식은
- 숫자 자체가 너무 커질 수 있고
- 문자열을 계속 이어붙이고
- 매번
atoll()로 바꾸는 과정도 비효율적이라
시간 초과나 범위 문제를 피할 수 없었습니다.
풀이 아이디어
이 문제에서 중요한 것은 실제 수 전체를 아는 것이 아니라,
그 수를 n으로 나눈 나머지가 0인지 여부입니다.
즉, 큰 수를 직접 만들 필요 없이
현재까지의 나머지만 관리해도 충분합니다.
예를 들어 현재 수가 ret이고, 여기에 뒤에 1을 하나 붙이면 새 수는
ret * 10 + 1이 됩니다.
그런데 실제 전체 값을 다 만들지 않고도,
(ret * 10 + 1) % n만 계산하면 다음 상태를 이어갈 수 있습니다.
즉, 매번 나머지만 유지하면 숫자 크기를 크게 만들지 않고도 문제를 해결할 수 있습니다.
성공한 코드
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
while (scanf("%d", &n) != EOF) {
int cnt = 1;
ll ret = 1;
while (true) {
if (ret % n == 0) {
cout << cnt << "\n";
break;
} else {
ret = (ret * 10) + 1;
ret %= n;
cnt++;
}
}
}
return 0;
}풀이 흐름
- 입력을 파일 끝까지 반복해서 받는다.
- 현재 수를 직접 저장하는 대신, 현재 나머지를 의미하는 값
ret를 사용한다. - 처음 값은
1로 시작한다. ret % n == 0이면 현재 자리수cnt를 출력한다.- 아니라면 다음 수를 만드는 방식인
ret = ret * 10 + 1을 적용한다. - 바로
% n을 적용해 숫자 크기를 줄인다. - 이 과정을 반복한다.
구현 포인트
1. 큰 수를 직접 만들지 않기
이 문제는 111111... 형태의 수가 매우 커질 수 있기 때문에,
숫자 전체를 직접 저장하는 방식으로는 해결하기 어렵습니다.
그래서 실제 수가 아니라 나머지 값만 유지하는 방식으로 바꿨습니다.
ret = (ret * 10) + 1;
ret %= n;이렇게 하면 수는 커지지 않고, 필요한 정보만 유지할 수 있습니다.
2. 모듈러 연산을 미리 적용하기
핵심은 매 단계마다 바로 % n을 적용하는 것입니다.
즉,
- 먼저 큰 수를 만들고 나중에
% n을 하는 것이 아니라 - 중간중간 바로 모듈러 연산을 적용해서 숫자 크기를 줄이는 것
이 중요했습니다.
이 덕분에 long long 범위를 넘지 않으면서도 계속 계산할 수 있었습니다.
3. 여러 테스트 케이스 처리
입력은 테스트 케이스 개수가 따로 주어지는 것이 아니라,
입력이 끝날 때까지 계속 주어집니다.
그래서 아래처럼 EOF까지 반복하는 방식으로 처리했습니다.
while (scanf("%d", &n) != EOF)이 문제에서는 이 입력 처리 방식도 같이 익혀둘 만한 포인트였습니다.
