백준 1407: 2로 몇 번 나누어질까

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

 

이 문제는 처음 봤을 때, 구간의 끝 값을 2로 나눠서 어떻게 해볼 수 없을까? 부터 생각을 하였다.

하지만, 아무리 끝 값을 이것저것 굴러보아도 답이 나오지 않아서 포기하려던 찰나 다른 문제에서 해결했던 방법이 떠올랐다.

 

바로 누적합이다. 이전까지 누적합은 배열 내에서만 사용을 했었는데, 이전에 풀었던 문제 중에 숫자 구간 합을 누적합을 이용해 해결했었던게 인상깊었던 문제가 있었다. 즉, [A, B] 구간의 합을 ([1, B] 구간의 합) - ([1, A - 1] 구간의 합) 으로 바꾸는 것이다.

 

그렇다면 이 문제도 이렇게 해결 할 수 있을 것이다. 그럼, [1, A] 구간의 합을 어떻게 구할 수 있을까? 나는 여기에 직면하게 된다. 규칙을 찾아보기 위해서는 일일히 나열하는 것이 제일이다. A가 17일 경우를 한번 가정을 해서 나열을 하면 다음과 같다.

 

f(1) = 1

f(2) = 2

f(3) = 1

f(4) = 4

f(5) = 1

f(6) = 2

f(7) = 1

f(8) = 8

f(9) = 1

f(10) = 2

f(11) = 1

f(12) = 4

f(13) = 1

f(14) = 2

f(15) = 1

f(16) = 16

f(17) = 1

그럼 홀수가 1이란 값을 가진다란 것을 알 수 있다. 홀수의 갯수는 ceil(전체 갯수 / 2)이다. 그럼 홀수를 지워보자

f(2) = 2

f(4) = 4

f(6) = 2

f(8) = 8

f(10) = 2

f(12) = 4

f(14) = 2

f(16) = 16

이번엔 2를 가진 값이 일정 간격으로 반복되는 것을 확인할 수 있다. 이 갯수는 ceil(전체 갯수 / 2)이다. 이제 2를 지우자

f(4) = 4

f(8) = 8

f(12) = 4

f(16) = 16

이번엔 4를 가진 값이 일정 간격으로 반복된다.

...

[1, A] 구간의 f(x)의 합을 g(x)라 할 때, 이 규칙을 바탕으로 식을 세우면 다음과 같다.

g(x) = g(x / 2) + ceil(x / 2) * (pow(2, g(x) 반복 횟수))

 

규칙을 발견 이 식을 활용하면, f(x)의 [1, A] 구간의 합을 쉽게 구할 수 있다.

그렇게 식을 세운 나는 재귀를 활용해 문제를 해결하려했다.

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
ll A, B;

ll solve(ll n, ll d)
{
	if (n == 0) return 0;
	return solve(n / 2, d * 2) + d * ceil((double)n / 2.0);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> A >> B;
	cout << solve(B, 1) - solve(A - 1, 1) << '\n';
}

그런데, 놀랍게도 틀렸다. 점화식을 잘못 세운 것인지 잠깐 의심이 든다.

다만 경험상 이런 오류는 자료형 문제가 많았다. 그러면 ceil 사용이 잘못되었는지 의심이 들었다. 그래서 이번엔 if문을 사용해보자.(여기선 편리하게 삼항연산자를 사용했다)

#include <iostream>
using namespace std;
using ll = long long;
ll A, B;

ll solve(ll n, ll d)
{
	if (n == 0) return 0;
	ll s = (n % 2 > 0) ? (n / 2 + 1) : n / 2;
	return solve(n / 2, d * 2L) + d * s;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> A >> B;
	cout << solve(B, 1) - solve(A - 1, 1) << '\n';
}

이번엔 맞았다. 앞으로도 double과 long long에 자료형 변환에 주의하자.