[BOJ] 백준 16723 원영이는 ZOAC과 영원하고 싶다

문제 링크

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

수학문제이다.

나는 아래처럼 풀었다.

정답을 $p$라 하고, $n$이 충분히 크다고 가정하자.

$p = 2 + 4 + 6 + 8 + 10 + 12 + ...$

$= 2(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + ... )$

$= 2(1 + 3 + 5 + ... + 2(1 + 2 + 3 + ...) )$

이런식으로 짝수들을 계속 2로 묶어가며 수를 절반씩 줄여갈 수 있다.

이를 적당히 구현해보자!

정답 코드

	#include <iostream>
	using namespace std;
	using ll = long long;
	ll n, ans;
	int main() {
	cin >> n;
	ans = 2 * n;
	for (ll i = 1; n / 2 > 0; i++, n /= 2) {
	ans += (1 << i) * (n / 2);
	}
	cout << ans;
	}

view raw 16723.cpp hosted with ❤ by GitHub