[C++] 비트가 넘쳐흘러 (백준 17419번)

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

 

#include <iostream>
#include <string>
using namespace std;

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

    int n;
    string k;
    cin >> n >> k;

    int cnt = 0;
    for (char c: k) {
        if (c == '1') cnt++;
    }

    cout << cnt << '\n';
}

처음에는 n 크기를 k크기로 잘못봐서 그냥 0이 될 때까지 연산을 계속하도록 했다. 그랬더니 서브태스크 1도 못함...ㅎ (WA) 생각해보니 이진수의 자리수가 1,000,000까지 될 수 있다는 거니까 일단 식의 규칙을 찾고 정수가 아니라 문자열로 다뤄야겠다고 생각했다. 한번만 해보니까 바로 규칙을 찾을 수 있었다. 연산을 한번 하면 이진수에서 가장 오른쪽에 있는 1이 0으로 바뀐다. 즉, 모든 수를 0으로 만드려면 연산을 1의 총 개수만큼 하면 된다. 그럼 끝~ (AC)