BOJ 28507 Баланс настроения

문제 요약

$i = 1 \cdots N$까지 다음 중 하나의 작업을 순서대로 진행합니다.

• 부정적인 생각하기 — $x$가 $x-1$이 됩니다.
• 애매한 생각하기 — $x$가 $2(x+i-2)$가 됩니다.

$x$는 처음에 $0$이고, $N$개의 작업을 모두 진행한 뒤에도 $0$이어야 합니다.

부정적인 생각의 횟수를 최소화하면서 작업을 진행하는 방법을 찾으세요.

관찰

애매한 생각에서 튀어나오는 $2i$를 없애고 $i$의 값에 상관없이 작동하는 작업으로 만들고 싶습니다. $x$가 2배로 늘어나고 뒤에 $2i$가 따라붙는 걸 마치 $2i$도 2배됨에 의한 결과로 생긴 것처럼 생각할 수 있게끔 값을 조정합니다.

$y = x+2i$ 를 정의하겠습니다.

$i+1$번째 작업으로 부정적인 생각을 하면 $x$가 $x-1$이 되고, 이때 $y$는 $x+2i$에서 $x-1+2i+2 = x+2i-1 = y+1$이 됩니다.

$i+1$번째 작업으로 애매한 생각을 하면, $x$가 $2(x+i-1)$이 되고, 이때 $y$는 $x+2i$에서 $2(x+i-1)+2i+2 = 2(x+2i) = 2y$가 됩니다.

즉 두 작업을 각각 +1과 ×2 연산으로 바꿔 생각할 수 있습니다.

처음에 $y = 0$이고, 목표는 $i = N$일 때 $y = 2N$으로 만드는 것으로 바뀝니다.

연산 매기기

주어진 연산은 어떤 수를 이진 표현으로 보았을 때 필요한 자리를 1로 만들면서 왼쪽으로 밀어주는 방법으로 4 이상의 모든 정수를 주어진 횟수의 연산 안에 만들어낼 수 있으며, 이것이 +1 연산을 최소로 쓰는 방법입니다.

그러니 $2N$을 이진 표현으로 나타낸 뒤에, 맨 뒷자리부터 역순으로 +1 ×2 를 해야 하는지 혹은 그냥 ×2만 하면 되는지를 판별해주면 $\mathcal{O}(\log N)$만에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	ll n, now; cin >> n; now = n; n <<= 1;
	stack<ll> ans;
	while(n){
		if(n&1) ans.push(now--);
		now--;
		n >>= 1;
	}
	cout << ans.size() << '\n';
	while(ans.size()){
		cout << ans.top() << ' '; ans.pop();
	}
}