[C++] 백준 1094번 막대기

1. 문제이해

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

1094번: 막대기

 

길이가 64cm인 막대기를 이용해 길이가 Xcm인 막대기를 만들려고 한다.

단, 막대기는 절반으로만 자를 수 있으며, 남은 길이의 합이 X보다 크면, 자르고 남은 막대는 버려야 한다.

이때, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

문제가 복잡해보이지만, 사실 간단한 문제이다.

처음 주어진 막대의 길이는 64cm 이고, 절반으로만 막대를 자를 수 있다.

그렇게 되면, 순수하게 잘라서 만들 수 있는 막대의 길이는

64, 32, 16, 8, 4, 2, 1이다.

위의 7개의 수들에는 공통점이 있다. 모두 2의 N제곱수라는 점이다.

 

그렇다면 예제입력 1의 경우를 보자.

만들고자 하는 막대 X의 길이는 23cm이다.

23cm를 만들기 위해서 위 7개의 숫자를 조합하면,

23 = 16 + 4 + 2 + 1

23은 16, 4, 2, 1이라는 2의 제곱수의 합으로 이루어진 수이므로,

총 4번의 풀칠이 필요하다.

여기서, 23을 2의 제곱수들만으로 이루어지므로, 다음과 같이 나타낼 수 있다.

23 = 10111 (2)

십진수 23을 2진수로 나타내면 10111로 나타낼 수 있으며,

여기서 1인 부분은 각각 16, 4, 2, 1로, 1인 부분의 개수가 풀로 붙여야하는 막대의 개수가 된다.

 

즉, 문제에서 요구하는 X를 만들기 위해 풀로 붙여야 하는 막대의 개수는

X를 2진수로 나타냈을때의 1인 부분의 개수와 동일하다.

 

그렇다면, 10진수를 2진수로 어떻게 바꾸어야 할까? 아래 그림을 통해 알아보자.

 

 

10진수를 2진수로 바꾸기 위해서는, 위와 같이 2로 나눈 나머지 값을 이용하면 된다.

2로 나눠진 나머지 값 x 10의 N제곱을 더해나가면 해당 수를 2진수로 변환 할 수 있다.

이러한 알고리즘을 이용해 작성한 코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
#include <string>
using namespace std;

// 십진수를 이진수로 바꾸는 함수
int tentotwo(int num) {
	int result = 0;
	int remain;
	int i = 1;

	// 2로 나눌 때의 나머지를 이용한 변환법
	while (num > 0) {
		remain = num % 2;
		result += remain * i;
		num /= 2;
		i *= 10;
	}

	return result;
}


int main() {
	int X;               // 만들고자 하는 막대의 길이
	string convert_num;
	int count = 0;       // 붙여야하는 횟수

	cin >> X;

	// 변환된 이진수 값을 문자열로 변환
	// 문자열 앞에서부터 1인 부분의 개수를 세어줌
	// 1 = 붙여야하는 막대기에 해당하는 부분
	convert_num = to_string(tentotwo(X));
	for (int i = 0; i < convert_num.size(); i++) {
		if (convert_num[i] == '1') {
			count++;
		}
	}

	cout << count;

	return 0;
}

먼저 tentotwo 함수는 십진수를 이진수로 변환하는 함수로,

매개변수 num 값을 2로 나눠가며, 해당 부분의 나머지를 이용해 이진수로 변환한다.

 

메인함수에서는 만들고자 하는 막대의 길이 X를 입력받고,

X를 2진수로 변환, 2진수로 변환된 값을 문자열로 한번 더 변환한다.

문자열로 변환한 후에는, 1의 개수가 곧 필요한 막대의 개수이므로, 

for문을 통해 앞에서부터 1의 개수를 카운트한다.

마지막으로 카운트된 1의 개수를 출력해주면 된다.

 

 

---

2진수로 바꾸어 푸는 문제임을 빨리 알아차리면 쉽게 풀 수 있는 문제였다.

다행히도 2진수로 바꾸는 문제라는 걸 금방 알아차려서 비교적 쉽게 풀 수 있었다.😊