알고리즘 :: 백준 :: 4375 - 1

 

 

 

 

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

입력: 각 테스트케이스마다 2와 5로 나누어 떨어지지 않는 정수 N(1 ≤ N ≤ 10000)

출력: 각 자릿수가 모두 1로만 이루어진 n의 배수의 자릿수

✏️ 문제풀이

[Tip] 정해지지 않은 입력 개수 입력받기 = `while (cin >> n)`

 

1. 증명하기

이 문제는 정답을 정수 자료형에(`int`(12자리), `unsigned long long`(20자리)) 담을 수 없습니다.

따라서 구해야하는 답인 '자릿수'에 집중해봅시다.

 

$x$가 n의 배수라는 뜻은, $x \pmod n = 0$ 이라는 뜻입니다.

그리고, 모듈로 연산(`%`)은 분배법칙이 성립합니다.

 

• $x \pmod n = 0$ 이고, $x$를 이전 규칙으로 표현하면 $((x\div10) - 1) \times 10 + 1$입니다.
• $((x\div10) - 1)$를 $x'$ 이라고 생각하면, $x \pmod n = (x' \times 10 + 1) \pmod n$ 입니다.
  
  • 모듈로 연산자는 분배법칙이 가능하므로
  • $x \pmod n = (x' \times 10) \pmod n + 1 \pmod n = (x' \pmod n\times 10) \pmod n + 1$
• 즉, 1, 11, 111, ... 이렇게 10을 곱하고 1을 더해가는 것과
  이전 단계의 수에 모듈로 연산한 나머지에 10을 곱하고 1을 더해가는 것은 똑같음을 증명했습니다.

2. 예시로 이해하기

n = 9901일 때

• `target = 1, 11, 111, 1111`은 넘어가고
• `target = 11111`일 때, `% n`은 1210,
• `target = 111111`일 때 `% n`은 앞에서 구한 1210에 `% n` 한 것과 같습니다. `10 * 1210 + 1 = 12101 % n`은 2200
• `target = 1111111`일 때 `% n`은 앞에서 구한 2200에 `% n`한 것과 같습니다. `10 * 2200 + 1 = 22001 % n`은 2199
• 이를 반복하면, 2199 → 2189 → 2089 → 1089 → 990 → 0

12번째 반복 때 0이 나왔으므로 `target`은 12자릿수입니다.

 

📝 코드

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

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int N;
	while (cin >> N) {
		int result = 0, num = 0;
		do {
			num = (10 * num + 1) % N;
			result++;
		} while (num != 0);
		cout << result << '\n';
	}
}

 

🔗 코드 링크

🕧 결과