취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14265번 문제인 영선 수열이다.
문제는 아래 링크를 확인하자.

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

어떤 수가 홀수이면 1을 빼고 짝수이면 2로 나누는 것을 이진수의 관점에서 해석해보자. 그러면 주어진 수열은 일의자리가 1일 때는 일의자리를 0으로 바꾸고, 아니라면 마지막 0을 지우는 것을 반복하는 것으로 볼 수 있다. 이 과정을 역으로 해석하면, X에서 시작해 Y에 도달하기 위해서는 Y의 자릿수가 (이진수 기준) X로 시작하거나 X가 짝수인 경우 X+1로 시작해야만 함을 알 수 있다.

이를 이용해 Y를 가능한 각 자릿수별로 세어 문제를 해결하자.

구현 방식에 따라 X가 0으로 주어지는 경우에 유의할 필요가 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll K, KK, A, B, tmp;
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K >> A >> B; KK = K + 1; B++; tmp = K;
	if (!K) {
		cout << B - A;
		return 0;
	}
	while (K < B) {
		if (A < KK) ans += min(B, KK) - max(A, K);
		K <<= 1, KK <<= 1;
	}
	if (tmp % 2 == 0) {
		K = tmp + 1, KK = tmp + 2;
		while (K < B) {
			if (A < KK) ans += min(B, KK) - max(A, K);
			K <<= 1, KK <<= 1;
		}
	}
	cout << ans;
}