17419번: 비트가 넘쳐흘러

문제 출처 : https://www.acmicpc.net/problem/17419

 

언어 : Kotlin

 

문제 설명 :

DJ욱제는 비트에 심취한 나머지, 비트를 비틀어 제껴버리는 문제를 내 버렸다!
N자리 이진수 K가 주어진다. K가 0이 아닐 때까지 아래의 연산을 적용했을 때, 연산이 일어나는 횟수를 구하시오.

• K = K-(K&((~K)+1))

 

아래는 위의 연산에 사용된 연산자에 대한 설명이다.

• '+'는 산술 더하기 연산이다. (5 + 2 = 7)
• '-'는 산술 빼기 연산이다. (5 - 2 = 3)
• '&'는 비트 AND 연산이다. (1101 & 0111 = 0101)
• '~'는 비트 NOT 연산이다. 켜진 비트를 끄고, 꺼진 비트를 켜는 연산이다. (~1101 = 0010)

 

입력 :

첫째 줄에 N이 주어진다.

둘째 줄에 N자리 이진수 K가 주어진다. K는 0으로 시작하지 않는다. 즉, leading zero는 없다.

 

출력 :

연산이 일어나는 횟수를 출력한다.

 

서브태스크 1 (51점) :

이 서브태스크는 다음의 조건을 만족한다.

• 1 ≤ N ≤ 30

 

서브태스크 2 (49점) : 

이 서브태스크는 추가 제한 조건이 없다.

 

제한 사항 :

• 시간 제한 : 1초 (추가 시간 없음)
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
5 10110	3

 

풀이 : 

1. 컴퓨터에서 음수 저장시, 절댓값의 2의 보수를 저장.
2. 2의 보수를 만드는 건 모든 비트를 반전시킨 뒤 1을 더하기.

위 전제 하, (~K) + 1은 -K이다.

즉, K = K - (K & -K)이다.

 

K & -K는 펜윅 트리 알고리즘을 알면 이해할 수 있다.

 

펜윅 트리 알고리즘이란 세그먼트 트리의 변형으로 수열의 구간 합을 빠르게 구할 수 있도록 고안된 자료 구조이다.

아무튼 이 펜윅 트리 알고리즘을 구현하기 위해 비트 연산, 0이 아닌 최하위 비트 값을 알아야 한다.

 

이 최하위 비트 값은 예를들어 다음과 같다.

3 = (11)₂

5 = (101)₂

6 = (110)₂

8 = (1000)₂

즉, i 값의 최하위 비트는 i & -i 이다.

이 말은 곧 가장 뒤에 있는 1의 위치를 알아내라는 것이다.

 

맨 뒤의 1의 위치를 알아 낸 후, 그 비트를 0으로 바꾸는 연산이 문제에서 주어진 식이다.

주어진 비트열에서 1의 개수가 곧 답이 된다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    val n = readLine().toInt()
    bw.write("${readLine().count { it == '1' }}")
    bw.flush()
    bw.close()
}