백준 - 07

2089번 - -2진수

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다.

10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오.

---

풀이

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim();

let N = Number(input);
let answer = N ? "" : 0;

while (N != 0) {
  if (N % -2) {
    answer = "1" + answer;
    // -2로 나누었을 때 나머지가 있다면 주어진 값에 1을 뺸 후 몫을 계산합니다.
    N = (N - 1) / -2;
  } else {
    answer = "0" + answer;
    N /= -2;
  }
}

console.log(answer);

---

17103번 - 골드바흐 파티션

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다.
짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자.
두 소수의 순서만 다른 것은 같은 파티션이다.

---

풀이

1. 입력 값의 max 값까지의 소수들을 구합니다.
2. 각 소수별 골드바흐의 추측에 해당하는지 검사합니다.
3. 3,5 과 5,3처럼 순서만 바뀐 쌍은 제외하기위해 해당하는 소수(p1)를 배열에 저장합니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map(Number);

let n = input.shift();
let max = Math.max(...input);

let primes = getPrimes(max);

let answer = [];

for (let x of input) {
  answer.push(goldbarh(x, primes));
}

console.log(answer.join("\n"));

function getPrimes(n) {
  let arr = new Array(n)
    .fill(0)
    .map((_, i) => i)
    .fill(0, 0, 2);

  for (let i = 2; i < n; i++) {
    if (arr[i]) {
      for (let j = i * i; j < n; j += i) {
        arr[j] = 0;
      }
    }
  }

  return arr.filter((x) => x != 0);
}

function goldbarh(x, primes) {
  let p1Arr = [];

  for (let p1 of primes) {
    let p2 = x - p1;

    if (primes.includes(p2) && !p1Arr.includes(p2)) {
      p1Arr.push(p1);
    }
  }

  return p1Arr.length;
}

• 시간초과..

---

다른 풀이

• 시간 단축을 위해 골드바흐의 추측을 검사할 때 입력 값의 절반인 소수만 검사합니다.

• primes 배열을 소수 값에서 소수인지만 판별하는 boolean 값으로 변경해 map, filter 등을 없애 시간을 단축합니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map(Number);

let n = input.shift();
let max = Math.max(...input);

let primes = getPrimes(max);

let answer = [];

for (let x of input) {
  answer.push(goldbarh(x, primes));
}

console.log(answer.join("\n"));

function getPrimes(n) {
  let primes = new Array(n).fill(true).fill(false, 0, 2);

  for (let i = 2; i < n; i++) {
    if (primes[i]) {
      for (let j = i * i; j < n; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes;
}

function goldbarh(x, primes) {
  let cnt = 0;

  for (i = 2; i <= x / 2; i++) {
    if (primes[i] && primes[x - i]) {
      cnt++;
    }
  }

  return cnt;
}

---

11576번 - Base Conversion

A진법으로 나타낸 숫자를 B진법으로 변환시켜주는 프로그램을 작성하기로 하였다.

N진법이란, 한 자리에서 숫자를 표현할 때 쓸 수 있는 숫자의 가짓수가 N이라는 뜻이다. 예를 들어 N이 17일 때 한 자릿수에서 사용할 수 있는 수는 0, 1, 2, … , 16으로 총 17가지가 된다.

입력의 첫 줄에는 미래세계에서 사용하는 진법 A와 정이가 사용하는 진법 B가 공백을 구분으로 주어진다. A와 B는 모두 2이상 30이하의 자연수다.

입력의 두 번째 줄에는 A진법으로 나타낸 숫자의 자리수의 개수 m(1 ≤ m ≤ 25)이 주어진다. 세 번째 줄에는 A진법을 이루고 있는 숫자 m개가 공백을 구분으로 높은 자릿수부터 차례대로 주어진다. 각 숫자는 0이상 A미만임이 보장된다. 또한 수가 0으로 시작하는 경우는 존재하지 않는다.

---

풀이

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

let [a, b] = input[0].split(" ").map(Number);
let n = Number(input[1]);
let numbers = input[2].split(" ").reverse().map(Number);

let sum = 0;

for (let i = 0; i < n; i++) {
  sum += a ** i * numbers[i];
}

let answer = [];

while (sum > 0) {
  answer.push(sum % b);
  sum = Math.floor(sum / b);
}

console.log(answer.length ? answer.reverse().join(" ") : 0);

---

1463번 - 1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.

연산을 사용하는 횟수의 최솟값을 출력하시오.

---

풀이

시간 제한이 0.15초 => DFS를 이용해 풀면 시간 초과가 됩니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim();

let num = Number(input);

let answer = new Array(num + 1).fill(num);

function DFS(N, cnt) {
  if (N < 1) return;

  if (N == 1) {
    answer[N] = Math.min(answer[N], cnt);
  }

  if (N % 3 == 0) {
    answer[N / 3] = Math.min(answer[N / 3], cnt + 1);
    DFS(N / 3, cnt + 1);
  }

  if (N % 2 == 0) {
    answer[N / 2] = Math.min(answer[N / 2], cnt + 1);
    DFS(N / 2, cnt + 1);
  }

  if (N - 1 >= 1) {
    answer[N - 1] = Math.min(answer[N - 1], cnt + 1);
    DFS(N - 1, cnt + 1);
  }
}

DFS(num, 0);

console.log(answer[1]);

---

다른 풀이

DP로 풀어봅시다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim();

let num = Number(input);

let answer = new Array(num + 1).fill(0).fill(1, 2, 4);

for (let i = 4; i <= num; i++) {
  answer[i] = answer[i - 1] + 1;

  if (i % 2 == 0) {
    answer[i] = Math.min(answer[i / 2] + 1, answer[i]);
  }

  if (i % 3 == 0) {
    answer[i] = Math.min(answer[i / 3] + 1, answer[i]);
  }
}

console.log(answer.pop());