백준 1094. 막대기

백준 1094. 막대기

구현문제를 연습하다가 신기한 문제가 있어서 가져옴

1. 문제 분석

64cm 막대를 반으로 쪼개서 Xcm 막대를 만들기

막대기가 몇개 필요한지 묻는 문

설명이 상당히 애매하게 되어있는데 번역문제라 그런듯

입력

• 만들어야하는 길이 Xcm가 주어짐. X는 64보다 작거나 같은 자연수

출력

• 몇개의 막대를 풀로 붙여서 Xcm를 만들수 있는지 개수를 출력

예시 분석

1) 23

64를 잘 쪼개서 23을 만들어야한다

1. 초기 막대 64
2. 64 > 23 이므로, 64를 반으로 자름. 현재 가진 막대 : (32, 32)
3. 남은 막대들의 합(32)이 23보다 크거나 같으므로, 하나를 버림(32). 현재 가진 막대 (32)
4. 32 > 23 이므로, 32를 반으로 자름. 현재 가진 막대 : (16, 16)
5. 남은 막대들의 합(16)이 23보다 작으므로, 둘 다 가짐. 현재 가진 막대 (16, 16)
6. 가장 짧은 막대(16)를 반으로 자름. 현재 가진 막대 : (16, 8, 8)
7. 남은 막대들의 합(16 + 8)이 23보다 크거나 같으므로, 하나(8)를 버림. 현재 가진 막대 (16, 8)
8. 가장 짧은 막대(8)을 반으로 자름. 현재 가진 막대 : (16, 4, 4)
9. 남은 막대들의 합(16 + 4)이 23보다 작으므로 둘 다 가짐. 현재 가진 막대 (16, 4, 4)
10. 가장 짧은 막대(4)를 반으로 자름. 현재 가진 막대 : (16, 4, 2, 2)
11. 남은 막대들의 합(16+4+2)이 23보다 작으므로 둘 다 가짐 : (16, 4, 2, 2)
12. 가장 짧은 막대(2)를 반으로 자름. 현재 가진 막대 : (16, 4, 2, 1, 1)
13. 남은 막대들의 합(16+4+2+1)이 23과 같으므로, 하나(1)를 버림. 현재 가진 막대 (16+4+2+1)
14. 최종적으로 가진 막대들의 합이 X=23이 되었으므로 4개의 막대를 합하면 된다 출력 : 4

알고리즘

이해하기 쉽게 설명하면 가장 큰 막대를 들고 얘를 쓸지 말지 결정하는 것이다

이 막대가 너무 길어서 못쓴다면 반으로 쪼개고

이 막대를 쓸거라면, 그대로 놔둔다

64? 너무 큼, 32? 너무 큼, 16? 쓸만함. 앞으로 7cm 더 만들어야하므로

아까 16 자르면서 나온 8cm 가져옴. 8cm 너무 큼, 4cm 쓸만함

…

이런식으로 반복하면 다음과 같이 정리할 수 있다

1. stick을 64로 놓음
2. 더 늘려야할 길이 X가 남아있는 동안 다음을 반복함
    2-1. 현재 손에 든 stick이, 남은 길이 X보다 긴가?
        - 길다면 이 길이는 못쓰므로, 절반으로 쪼갠다 (stick = stick / 2)
    2-2. 작거나 같다면 쓸 수 있으므로, 기록해둠
        - 길이를 만들었으므로, 만들어야하는 길이를 줄인다. (X = X - stick)
        - 이 막대는 썼으니, 다음으로 작은 막대를 집음 (stick = stick / 2)

이런식으로 구현하면 되지만 더 쉬운 방법이 있음

문제를 잘 보면, 모든 길이가 2의 배수라는것을 알 수있는데

특히 해당 길이를 사용하느냐(1) 마느냐(0)으로 나눠지는 것을 알 수 있다

(64, 32, 16, 8, 4, 2, 1) 각 길이를 사용하느냐 마느냐로 나눌 수 있는데

23은 16, 4, 2, 1을 사용하므로

(0, 0, 1, 0, 1, 1, 1)로 나타낼 수 있다.

이는 이진수 표현과 같으므로

X를 이진수로 변환하고 1이 몇개있는지만 체크하면

훨씬 쉽게 풀이할 수 있다

소스코드

구현 풀이 방법

#include <iostream>

using namespace std;

int main() {
	int X;
	cin >> X;

	int stick = 64;
	int cnt = 0;

	while (X > 0) {
		if (stick > X) {
			stick /= 2;
		}

		else {
			cnt++;
			X -= stick;
			stick /= 2;
		}
	}
	cout << cnt;

	return 0;
}

C++ bitset 라이브러리를 이용한 방법

#include <iostream>
#include <bitset>

int main() {
	int x;
	std::cin >> x;
	std::bitset<7> ans = x;
	std::cout << ans.count();
}

문제의 설명이 복잡하게 되어있지만, 예제를 따라가다보면

결국 2의 거듭제곱 수들의 조합으로 수를 만드는 것과 같다는 것을 알 수 있다

이는 곧 이진법 표현과 직접적으로 연결된다

많은 문제들이 이처럼 핵심 아이디어를 다른 방식으로 포장하여 표현하므로,

문제 핵심 아이디어가 무엇인지를 빨리 찾는게 중요하다는것을 느꼈음