A → B

문제

언어

  • JavaScript

순서도

  1. b 를 a 로 만드는 과정 수행
    • b 를 2 로 나눌 수 있다면, 2 로 나누기
    • b 의 뒤에서 1 을 제거할 수 있다면, 1 제거하기
  2. 1 번 과정 중, a 로 만들 수 없다면 -1 출력
  3. 1 번 과정 중, a 로 만들 수 있다면 횟수 출력

문제 풀이 step 1

  • 정수 A 를 B 로 바꾸려고 합니다. 가능한 연산은 다음과 같은 두 가지입니다.
    • 2 를 곱한다.
    • 1 을 수의 가장 오른쪽에 추가한다.
  • A 를 B 로 바꾸는 데 필요한 연산의 최솟값을 구하는 문제입니다.

문제 풀이 step 2

  • 그리디 알고리즘을 적용하는 문제로, 매 상황에서 최적의 선택을 하는 방식을 이용합니다.
  • A 에서 B 로 바꾸지말고, B 에서 A 로 바꾸는 과정을 수행합니다.
    • B 가 2 로 나뉘면, 2 로 나누고 횟수를 갱신합니다.
    • B 의 가장 오른쪽에서 1 을 제거할 수 있다면, 1 을 제거하고 횟수를 갱신합니다.
    • 이 과정 속에서 더 이상 2 로 나눌 수 없거나, 1 을 제거할 수 없다면 -1 을 출력하면 됩니다.
  • 위 과정을 수행하고, B 가 A 로 바뀌었으면 횟수를 출력하고, 아니면 -1 을 출력합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

const solution = (input) => {
	let [a, b] = input[0].split(" ").map(Number);

	let ans = 0;
	while (a < b) {
		if (b % 2 === 0) {
			// 2 로 나뉘면, 2 로 나누기
			b /= 2;
		} else {
			// b 가 한자리수면 -1 출력
			if (b < 10) return -1;

			// b 의 마지막 글자가 1 이라면 제거, 그게 아니라면 -1 출력
			const strB = String(b).split("");
			if (strB[strB.length - 1] === "1") strB.pop();
			else return -1;

			b = Number(strB.join(""));
		}

		// 횟수 갱신
		ans += 1;
	}

	if (a === b) return ans + 1;
	return -1;
};

console.log(solution(input));