[JavaScript] 백준 - 투에-모스 문자열

Language/JavaScript

[JavaScript] 백준 - 투에-모스 문자열

어징베 2023. 5. 3. 21:19

문제출처: https://www.acmicpc.net/problem/18222

18222번: 투에-모스 문자열

0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에

www.acmicpc.net

문제풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input;
rl.on("line", (line) => {
  input = line.trim();
  rl.close();
});

rl.on("close", () => {
  console.log(solution(input).toString());
});

function solution(k) {
  k = BigInt(k);
  if (k === 1n) return 0n;
  let max = 1n;
  while (max * 2n < k) max *= 2n;
  let prev = solution(k - max);
  return 1n - prev;
}