Fly me to the Alpha Centauri

문제

언어

  • JavaScript

문제 풀이 step 1

  • 하나씩 그려보다가 특이점을 발견하게 되어서 풀 수 있었습니다.

  • 그리다보면 아래의 표를 얻을 수 있습니다. 저는 제곱수들을 이용해서 풀었습니다.

  • 거리 횟수 방법
    1 1 1
    2 2 11
    3 3 111
    4 3 121
    5 4 1211
    6 4 1221
    7 5 12211
    8 5 12221
    9 5 12321
    … … …
    16 7 1234321
    … … …
    25 9 123454321

문제 풀이 step 2

  • 제곱수들의 방법을 보시면 근호값을 기준으로 좌우가 딱 맞아떨어지며 1씩 감소합니다.
    • 4 = 121
    • 9 = 12321
    • 16 = 1234321
  • 제곱수와 제곱수 사이에는 짝수개의 수가 존재합니다.
    • 1 ~ 4 = 2개
    • 4 ~ 9 = 4개
    • 9 ~ 16 = 6개
  • 제곱수와 제곱수 사이에 존재하는 짝수개의 수들을 반으로 쪼개면, 반은 작은 제곱수의 개수에 + 1을 한 값이고, 반은 큰 제곱수의 개수와 같습니다.
    • 1 ~ 4 => 2와 3으로 나눌 수 있는데 2는 거리가 1인 경우의 횟수 + 1이고, 3은 거리가 4인 경우의 횟수와 같습니다.
    • 4 ~ 9 => 5, 6과 7, 8로 나눌 수 있는데 5, 6은 거리가 4인 경우의 횟수 + 1이고, 7, 8은 거리가 9인 경우의 횟수와 같습니다.
  • 그래서 제곱수인지 먼저 판별하고, 제곱수가 아니라면 어떤 제곱수와 어떤 제곱수 사이에 있는 수인지 판별하고, 위의 규칙을 적용해서 풀었습니다.

소스 코드

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

const checkSquared = (num) => num === Math.pow(parseInt(Math.sqrt(num)), 2);

const solution = (input) => {
	let T = parseInt(input[0]);

	let res = "";
	let index = 1;
	while (T-- > 0) {
		const [x, y] = input[index++].split(" ").map(Number);
		const length = y - x;
		const squaredLen = Math.sqrt(length);

		// 제곱수인 경우
		if (checkSquared(length)) {
			res += `${squaredLen * 2 - 1}\n`;
			continue;
		}

		// 제곱수가 아닌 경우
		const start = Math.pow(parseInt(squaredLen), 2);
		const end = Math.pow(parseInt(squaredLen + 1), 2);

		if (length - start < end - length) {
			res += `${Math.sqrt(start) * 2}\n`;
		} else {
			res += `${Math.sqrt(end) * 2 - 1}\n`;
		}
	}

	return res;
};

console.log(solution(input));