막대기

문제

• 백준 1094번 - 막대기

언어

• JavaScript

순서도

1. 64 부터 2 로 나누며, 나눈 값이 X 보다 작으면 그 값은 풀로 붙일 때 만들 수 있는 막대의 구성 요소에 포함
2. 그 구성 요소의 합이 X 가 될때까지 1 번 과정을 반복
3. 구성 요소의 개수 출력

문제 풀이 step 1

• 문제에서 원하는 것을 주어진 수 X 가 몇 개의 2 의 제곱수로 이루어져있는지 구하는 문제입니다. (단, 중복은 불가능합니다.)
• 단, 64, 32, 16, 8, 4, 2, 1 이렇게 내림 차순으로 비교해야 합니다.
• 이 때, 2 의 제곱수가 X 보다 작다면, X 에 포함되는 것입니다.
• X 에 포함되면, X 에서 그 제곱수를 빼주고 남은 X 에서 또 다른 2 의 제곱수가 몇 개 포함되는지 구하면 됩니다.
• 구한 개수를 출력하면 정답이 됩니다.
• 추가 설명은 주석에 작성하겠습니다.

소스 코드

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

const solution = (input) => {
	let x = Number(input[0]);

	let cnt = 0;
	// 시작은 64 부터
	let bar = 64;
	while (x !== 0) {
		// x 보다 막대기가 작다면 x 에 포함되는 것
		if (x >= bar) {
			x -= bar;
			cnt += 1;
		}

		// 막대기를 반으로 나누기
		bar /= 2;
	}

	return cnt;
};

console.log(solution(input));