최대공약수

문제

백준 1850번 - 최대공약수

언어

JavaScript

순서도

유클리드 호제법을 이용해서 최대공약수를 구하는 함수 구현
입력으로 주어지는 두 수의 최대공약수 구하기
두 수의 최대공약수만큼 “1” 을 이어붙인 문자열 출력

문제 풀이 step 1

모든 자리가 1 로만 이루어져있는 두 자연수 A 와 B 가 주어집니다. 이때 A 와 B 의 최대공약수를 구하는 문제입니다.
우선, 유클리드 호제법을 이용해서 최대공약수를 구하는 함수를 구현합니다.
그리고 두 자연수 A 와 B 의 최대공약수를 구합니다.
- 이 때, 입력되는 수는 2^63 으로 Number 가 표현할 수 있는 수를 넘어가기 때문에 BigInt 형으로 변환합니다.
- Number 가 표현할 수 있는 안전한 최대 정수는 2^53 - 1 로 9007199254740991 입니다. 이는 대략 9*10^15 입니다.
구한 최대공약수만큼 “1” 을 이어붙인 문자열을 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

Reference.

MDN - Number.MAX_SAFE_INTEGER

후기

꼭 다시 풀어볼 문제입니다.
본 문제를 통해 알 수 있었던 것은 1 로만 이루어진 수들의 최대공약수를 구할 때는 그 수들의 길이의 최대공약수를 구하면 된다는 것이었습니다.
하지만 이것이 왜 성립하는 지에 대한 의문을 해결하지 못했습니다.

소스 코드

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

// 유클리드 호제법을 이용한 최대공약수를 구하는 함수
const gcd = (a, b) => {
	if (b === 0n) return a;
	return gcd(b, a % b);
};

const solution = (input) => {
	// BigInt 형으로 변환
	const [a, b] = input[0].split(" ").map(BigInt);

	let res = "";
	const n = Number(gcd(a, b));
	// 최대공약수 만큼 1 을 이어붙인 문자열 출력
	for (let i = 0; i < n; i++) {
		res += "1";
	}

	return res;
};

console.log(solution(input));