17배

문제

언어

  • JavaScript

순서도

  1. N 을 4 번 거듭해서 더하기
  2. 거듭해서 더한 값에 N 더하기

문제 풀이 step 1

  • 주어진 이진수 N 에 17 을 곱한 다음 이진수로 출력하는 문제입니다.
  • 간단하게 이진수를 십진수로 변환한 다음에 17 을 곱하고 다시 이진수로 변환하면 되겠지만, N 은 최대 1000 자리이므로 십진수로 변환하면 너무 큰 수이기 때문에 불가능합니다.
  • 따라서 그냥 이진수 덧셈 로직을 구현하고 N 을 총 17 번 더한 결과값을 출력하면 됩니다.
  • 17 번 더하는 대신, 더한 값을 거듭해서 더하면 4 번 더하고, 마지막에 N 을 한 번 더해주면 원하는 값을 찾을 수 있습니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 다른 방법의 문제 풀이도 아래에 포스트했습니다.

소스 코드

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

// 이진수 덧셈 함수
const getSum = (binary1, binary2) => {
	let flag = 0;
	let [left, right] = [binary1.length - 1, binary2.length - 1];

	const result = [];
	while (true) {
		let [a, b] = [0, 0];
		if (left >= 0) a = Number(binary1[left--]);
		if (right >= 0) b = Number(binary2[right--]);

		const sum = a + b + flag;
		if (sum === 0) {
			result.push(`0`);

			flag = 0;
		} else if (sum === 1) {
			result.push("1");

			flag = 0;
		} else if (sum === 2) {
			result.push("0");

			flag = 1;
		} else {
			result.push("1");

			flag = 1;
		}

		if (left < 0 && right < 0) break;
	}
	if (flag === 1) result.push(flag);

	return result.reverse();
};

const solution = (input) => {
	const binary = input[0].split("");

	// 4 번 거듭 제곱
	let base = [...binary];
	for (let i = 0; i < 4; i++) {
		base = getSum(base, base);
	}

	// 마지막으로 한 번 N 더하기
	base = getSum(base, binary);

	return base.join("");
};

console.log(solution(input));

다른 방식의 순서도

  1. N 에 2 를 4 번 곱하기
  2. 곱한 값에 N 더하기

다른 방식의 문제 풀이 step 1

  • N 이 이진수이기 때문에 이 방식을 사용할 수 있습니다.
  • N 에 2 를 4 번 곱하고, N 을 한 번 더한다면 17 배를 한 값과 동일해집니다.
    • 2 를 4 번 곱하는 것은 이진수를 왼쪽으로 4 번 쉬프트 하는 연산으로 구현하고,
    • 거기에 이진수 덧셈 연산 로직을 이용해서 N 을 한 번 더해주면 됩니다.
  • 추가 설명은 주석으로 작성하겠습니다.

다른 방식의 후기

  • 이 방법이 더 빠릅니다.
  • 이진수 연산 로직이 내부에 반복문이 있기 때문에 쉬프트 연산을 해주면 그만큼의 반복문 연산을 생략할 수 있기 때문에 더 빠릅니다.

다른 방식의 소스 코드

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

const getSum = (binary1, binary2) => {
	let flag = 0;
	let [left, right] = [binary1.length - 1, binary2.length - 1];

	const result = [];
	while (true) {
		let [a, b] = [0, 0];
		if (left >= 0) a = Number(binary1[left--]);
		if (right >= 0) b = Number(binary2[right--]);

		const sum = a + b + flag;
		if (sum === 0) {
			result.push(`0`);

			flag = 0;
		} else if (sum === 1) {
			result.push("1");

			flag = 0;
		} else if (sum === 2) {
			result.push("0");

			flag = 1;
		} else {
			result.push("1");

			flag = 1;
		}

		if (left < 0 && right < 0) break;
	}
	if (flag === 1) result.push(flag);

	return result.reverse();
};

const solution = (input) => {
	const binary = input[0].split("");

	// 이진수 맨 뒤에 0 을 4 번 넣어주는 것을 통해서 쉬프트 연산을 구현해줍니다.
	let base = [...binary, 0, 0, 0, 0];
	base = getSum(base, binary);

	return base.join("");
};

console.log(solution(input));