[C++] 백준 16282번 Black Chain

체인을 잘라서 1~N까지의 수를 만들 때 최소 몇번 잘라야하는지 구하는 문제입니다.

먼저 n번 잘랐을 때 최대 만들 수 있는 수를 구했습니다.
1번 = 2 1 4                             7
2번 = 3 1 6 1 12                      23
3번 = 4 1 8 1 16 1 32               63
4번 = 5 1 10 1 20 1 40 1 80       159
....

수를 보면 다음의 규칙을 가지고 있습니다. ((n + 1) * 1) + 1 + ((n + 1) * 2) + 1 ((n + 1) * 4) ......
하지만 이 방식으로 풀면 시간이 오래걸리므로 연산이 많이 필요하므로
1번 자르는것에 대한 최댓값에 대한 규칙을 찾아보면

1.  2 * (i + 1) - 1
2.  4 * (i + 1) - 1
3.  8 * (i + 1) - 1
4.  16 * (i + 1) - 1
....

공식을 보면 다음과 같습니다.
2^(i+1) * (i +1) - 1

이 공식을 이용해서 결과값을 도출해냈습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

int main(int argc, char* argv[])
{
	int i = 2;
	ll n;
	ll num = 2;
	ll sum;

	cin >> n;

	while (1) {
		num *= 2;
		sum = num * i - 1;

		if (sum >= n) {
			--i;
			break;
		}
		++i;
	}

	cout << i << "\n";

	return 0;
}