1

문제

• 백준 4375번 - 1

언어

• JavaScript

문제 풀이 step 1

• 주어진 n 에 대해서 1 로만 이루어진 n 의 배수를 찾아야합니다.
• 예를 들어, n 이 3 이라면 1, 11, 111, 1111, … 이런 모양의 수 중에서 3 의 배수를 찾아야 합니다.
• 그렇다면 완전 탐색 기법으로 1, 11, 111, 1111, … 을 하나씩 다 나머지 연산을 통해 검사해보면 됩니다.
• 하지만 이렇게 하면 시간 초과가 발생합니다.

문제 풀이 step 2

• 완전 탐색 기법으로 할 경우 1 이 정말 많아질 수 있습니다. (ex. 1111111111111111…)
• 1 이 정말 많아지면 연산의 시간 복잡도는 O(수의 길이) 가 됩니다.
• 그래서 시간 초과가 발생하는 것입니다.
• 그렇다면 어떻게 해야할까요??

문제 풀이 step 3

• 시간 초과를 피하기 위해서 나머지 연산의 특성과 1 로만 이루어진 수의 특성을 이용해야 합니다.
• 나머지 연산은 다음과 같은 수식이 성립합니다.
  • (A + B) % M = A % M + B % M
  • (A * B) % M = A % M * B % M
• 그리고 1 로만 이루어진 수들은 이런 성질을 가지고 있습니다.
  • 1 = 1
  • 11 = 1 * 10 + 1
  • 111 = 11 * 10 + 1
  • 1111 = 111 * 10 + 1
• 우리가 구해야 할 것은 “각 수가 주어진 n 으로 나눴을 때 나머지가 0 인가” 입니다.
• 위의 두 성질을 이용하면 다음과 같은 식을 만들 수 있습니다. (n 이 3 이라면)
  • 1 = 1
  • 11 % 3 = ((1 % 3 * 10 % 3) + 1 % 3) % 3
  • 111 % 3 = ((11 % 3 * 10 % 3) + 1 % 3) % 3
  • 1111 % 3 = ((111 % 3 * 10 % 3) + 1 % 3) % 3
• 식을 잘 보면 위에서 계산한 식이 다음 식에 포함되어 있다는 것을 알 수 있습니다.
• 이를 통해서 수의 길이를 줄여가며 검사해서 시간 초과를 피할 수 있습니다.
• 추가 설명은 주석에 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	let res = "";

	for (let i = 0; i < input.length; i++) {
		const n = parseInt(input[i]);

		let cnt = 1;
		let num = 1;
		while (true) {
			// 나머지 연산의 특성 덕분에 나머지 연산 후에도 다음 식에서 사용 가능
			num %= n;
			if (num === 0) break;

			// 1111... 의 성질을 이용한 수식
			num = num * 10 + 1;
			cnt += 1;
		}

		res += cnt + "\n";
	}

	return res;
};

console.log(solution(input));