문제 링크: https://www.acmicpc.net/problem/17419

 

\[K = K-(K\&((\sim K)+1))\]

위 식을 그대로 직접 구현해버리면 n이 최대 100만이기 때문에 시간초과입니다.

논리회로 시간에 배웠던걸 생각해보면 (~K)+1은 사실 -K를 2의 보수로 나타낸 것임을 알 수 있습니다. 그럼 위 식은 아래와 같이 바뀝니다

\[K = K-(K \& -K)\]

K & -K는 K에서 1인 비트중 최하위 비트입니다. 예를 들어 이진법으로 K=10110이라고 하면 (K & -K)는 00010이 됩니다. 노트에 적어보면 바로 이해가 됩니다. 펜윅트리 인덱스 계산할 때도 이 방식이 이용된다고 하네요.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	string s;
	cin >> n >> s;

	int counter = 0;
	for (auto& c : s)
		if (c == '1')
			++counter;

	cout << counter << '\n';

	return 0;
}
반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 1322: X와 K  (0) 2020.10.29
[백준][C++] 14719: 빗물  (2) 2020.09.19
[백준][C++] 17419: 비트가 넘쳐흘러  (0) 2020.08.30
[백준][C++] 1083: 소트  (0) 2020.08.29
[백준][C++] 3300: 무어 기계  (0) 2020.08.28
[백준][C++] 7595: Triangles  (0) 2020.08.27