[백준] 17419: 비트가 넘쳐흘러

문제 링크

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

접근 방식 / 풀이

문제를 읽으면서, 이 문제가 단순하게 K = K - (K & ((~K) + 1)) 이라는 연산을 여러 번 반복하라는 것은 아닐 것 같아 해당 식의 규칙을 고민해보았다.

예시

$K$가 1111일 때, 연산을 수행해 보자.

식을 자세히 들여다 보면, K와 ~K + 1을 and 연산을 수행시키는 것이 눈에 띄는데, 이 연산의 결과는 해당 이진수에서 제일 오른쪽에 있는 1만 빼내는 것이라는 것을 눈치챌 수 있다.

K가 1110이라면? 1110 & (0001 + 1) = 0010
K가 1100이라면? 1100 & (0011 + 1) = 0100

따라서, 이 연산은 K에서 제일 오른쪽에 나타나는 1을 제거하는 연산이라고 볼 수 있다.
이 연산은 K가 0이 아닐 때까지 (즉, K의 비트에 1이 존재하는 동안) 반복되기 때문에, 결론적으로 입력받은 비트의 1의 개수만큼 연산이 진행될 것이다.

결론은, K에 있는 1의 개수를 출력하는 것이 이 문제의 해답이다.
코드 작성은 쉬우나, 해당 연산의 규칙을 찾는 것이 관건인 문제였다.

답안 코드 링크 (Github)

Github Solution Link

정답 코드

#include <iostream>
#define fastio                      \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL)
using namespace std;

int main(void)
{
	char input[1000001];
	int n, ret = 0;

	fastio;
	cin >> n >> input;
	for (int i = 0; i < n; i++)
	{
		if (input[i] == '1')
			ret++;
	}
	cout << ret << "\n";
	return (0);
}