백준 17419번: 비트가 넘쳐흘러 (Python)

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

17419번: 비트가 넘쳐흘러

---

Solved By: Bitmasking

 

첫 시도에는 연산을 그대로 적용하여 k가 0이 될 때까지 count를 하며 결괏값을 구했지만 51점으로 문제를 맞히지 못했습니다.

 

그래서 주어진 연산을 반복하면서 나온 규칙이 짝수면 한 번에 1이 되는 것을 알고 제출했지만 틀렸었습니다.

(왜냐하면 2와 4만 했었기에 이런 규칙이 나왔었습니다. 너무 섣부른 판단이었습니다. 6을 했었다면 이 규칙은 성립되지 않습니다.)

 

그래서 여러 수들을 해보면 이진수의 맨 끝 1이 연산을 할 수록 하나씩 사라지는 것을 알 수 있습니다. 이를 통해 이번 문제는 주어진 이진수에서 1의 개수를 count 해주면 끝나는 문제입니다.

n = int(input())
k = input()
cnt = 0
for i in range(0, n):
    if k[i] == '1':
        cnt += 1
print(cnt)