백준 1094 < 막대기 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/1094

1094번: 막대기

 

📍알고리즘 분류

- 수학

- 비트마스킹

 

📍문제 풀이

64cm 의 막대기가 있을 때 이를 절반으로 쪼개면서 X cm로 만드려면 총 몇개의 막대기가 필요한지 구하라

 

✅비트마스킹을 통해 해결할 수 있다

이 문제는 10진수를 2진수로 바꾸는 과정과 상당히 유사하다!

 

✅예) X = 23 일 때, X를 2진수로 바꾸기

1. X > 0 이면 아래를 반복

1-1. X = X / 2 의 몫

1-2. X / 2의 나머지를 기록

 

2. X = 0 이면 기록한 나머지를 차례대로 나열

 

/*
        몫    나머지
23 / 2 	11      1
11 / 2	5       1
5 / 2	2       1
2 / 2	1       0
1 / 2	0       1

23 = 11101
*/

 

✅반면, 이 문제에서는 64에서 시작하여 절반으로 잘라나간다

/*
64 (2^6) : 1000000

절반으로 자르면, ( >> 1 )
32 (2^5) : 100000
16 (2^4) : 10000
8 (2^3) : 1000
4 (2^2) : 100
2 (2^1) : 10
1 (2^0) : 1

만약 X = 32, 16, 8, 4, 2, 1 이라면
답 : 1

만약 X = 48 (16 + 32) 라면?
48 = 2^5 + 2^4 : 110000
답 : 2

만약 X = 56 (8 + 16 + 32) 라면?
56 = 2^5 + 2^4 + 2^3 : 111000
답 : 3

...
*/

 

규칙성이 보인다

그리고 몇 개의 2제곱(0제곱 포함)으로 이루어져 있는지 구하면 되는 것을 알 수 있다

 

⭐즉, X를 2진수로 만들면서 몇 개의 1을 갖고 있는지(홀수이면 +1) 구하면 된다!

 

📍코드 (JavaScript)

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

let input;

rl.on("line", (line) => {
  input = line;
}).on("close", () => {
  let X = +input;
  let answer = 0;
  while (X > 0) {
    if (X % 2) answer++;
    X = parseInt(X / 2);
  }
  answer = answer <= 0 ? 1 : answer;
  console.log(answer);
});