[ICPC][BOJ] 16282 - Black Chain

문제 : https://www.acmicpc.net/problem/16282

---

[알고리즘 풀이]

이 문제의 핵심은 체인을 빼내면 항상 1g짜리 체인이 생기고, 체인이 1을 기준으로 왼쪽 / 1 / 오른쪽으로 3등분으로

나뉜다. 즉, 우리는 체인을 한 번 빼내면 다음과 같은 3개의 체인을 얻을 수 있다. K(g) / 1(g) / L(g)

 

우리는 체인을 빼내는 횟수를 최소화하고 싶으므로, i번 체인을 뺐을 때 최대 몇 g까지 표현이 가능한지를 생각해보자.

 

-체인을 1번 뺌-

K1 / 1 / K2 최대 3등분으로 나눠지고, 2가 없으므로 2가 필요하고, 2 / 1 이 있다고 가정하면 4가 필요하다.

즉, 최대 1번 체인을 빼서 1 + 2 + 4 = 7g 까지 표현이 가능하다.

-체인을 2번 뺌-

K1 / 1 / K2 / 1 / K3 최대 5등분으로 나눠지고, 1이 2개 있으므로 3이 필요하고, 1 + 1 + 3 = 5 이므로 6이 필요하고,

1 + 1 + 3 + 6 = 11이므로 12가 필요하다.

즉, 최대 2번 체인을 빼서 1 + 1 + 3 + 6 + 12 = 23g 까지 표현이 가능하다.

-체인을 i번 뺌-

i번 체인을 빼내면 1g짜리 체인이 i개 생긴 것이고, 최대 2 * i + 1개의 체인으로 나눠진다.

그러면 1g까지라 i개 있으므로, (i + 1) g짜리 체인이 필요하고,

그다음엔 1 * i + (i + 1) g까지는 표현이 가능하므로, (2 * i + 1) g짜리 체인이 필요하다.

이 과정을 반복하면 i번 체인을 빼냈을 때, 최대 2^(i + 1) * i + 2^(i+1) - 1 g까지 표현이 가능하다.

 

따라서, 체인을 빼내는 횟수를 늘려가며 최대 표현 가능한 g보다 n이 작아지는 순간 출력해주면 된다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	long long n;
	cin >> n;
	for (long long i = 1; ; i++) {
		long long total = i;
		for (int j = 0; j <= i; j++)
			total = total + (total + 1);
		if (n <= total){
			cout << i;
			return 0;
		}
	}
}

---