[C++] 백준 2205번: 저울 추 만들기

문제 링크

2205번: 저울 추 만들기

문제 요약

질량이 1부터 n까지인, 총 n개의 납덩이가 있고, 주석덩어리도 동일하게 존재한다. 납덩이와 주석덩어리를 하나씩 합쳐 저울 추를 만들 때, 저울 추가 모두 2의 거듭제곱꼴이 되도록 출력해야 한다.

접근 방법

규칙을 찾아보기 위해 n이 1일 때부터 한번 차례로 정답을 구해봤습니다.

1
1

1 2
1 2

1 2 3
3 2 1

1 2 3 4
3 2 1 4

1 2 3 4 5
1 2 5 4 3

1 2 3 4 5 6
1 6 5 4 3 2

1 2 3 4 5 6 7
7 6 5 4 3 2 1

1 2 3 4 5 6 7 8
7 6 5 4 3 2 1 8

이때 느낀 것이, 해를 뒤에서부터 구하는 것이 유리하다는 것을 알게 되었습니다. 예를 들어, n이 5일 때, 무게가 1인 덩이는 1, 3 두 가지를 선택할 수 있지만, 5인 덩이는 3 하나만 선택이 가능합니다. 그래서 뒤에서부터 제작이 가능한 가장 질량이 큰 무게추를 만들어 주는 식으로 그리디하게 코드를 짰습니다.

n이 10000이지만, 각 자리의 수에 대해, 2의 거듭제곱만 따져보기 때문에 시간복잡도는 $O(NlogN)$ 정도로 예상됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 10001;
bool visited[MAX];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	int limit = 1;
	while (limit <= n) limit *= 2;

	vector<int> ans;
	ans.reserve(n);
	for (int i = n; i >= 1; i--) {
		for (int j = limit; j >= 1; j /= 2) {
			if (!visited[j - i] && j - i <= n) {
				ans.push_back(j - i);
				visited[j - i] = true;
				break;
			}
		}
	}

	for (int i = ans.size() - 1; i >= 0; i--)
		cout << ans[i] << '\n';
	return 0;
}