1094 막대기

1094 막대기 (c++)

문제

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

접근 방식

구현

1. 64cm 길이의 막대를 Xcm로 만들고 싶다.
2. 아래를 반복
   1. 막대들의 총 합이 X보다 크다면
   2. 막대들 중 가장 작은 막대를 반으로 자르고
   3. 자른 막대의 반을 제외한 나머지의 합이 X보다 크다면 자른 막대의 반을 버린다.
3. 막대들의 길이의 총 합이 Xcm가 되었을 때, 막대의 갯수가 답

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
using namespace std;

int TotalLength = 64;
priority_queue<int> pq;
int X;

int main()
{
	cin >> X;

	pq.push(-TotalLength);

	while (true)
	{
		if (TotalLength > X)
		{
			int ShortestLength = -pq.top(); pq.pop();
			int HalfLength = ShortestLength * 0.5f;
			TotalLength -= HalfLength;
			pq.push(-HalfLength);
			if (TotalLength < X)
			{
				TotalLength += HalfLength;
				pq.push(-HalfLength);
			}
			else if (TotalLength == X) break;
		}
		else break;
	}

	cout << pq.size() << '\n';

	return 0;
}

다시 생각해 볼 점

1. 처음 코드를 짤 때, 가장 큰 막대를 자르고, 총 몇회를 반복했는지를 구하는걸로 착각하여 시간을 허비했다. 항상 문제를 정확히 읽고 구현해야하는게 무엇인지 명확하게 이해할 필요가 있다.
2. 가장 짧은 막대를 구하는 부부은 우선순위 큐를 사용했다.