백준 12931번 ) 두 배 더하기 (java)

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

12931번: 두 배 더하기

문제

풀이

이진수로 생각해서 풀어야 하는 풀이이다.

해당 숫자를 이진수로 변경하여 생각하면 *2 를 한느 경우는 이진수 자체를 < 연산하여 왼쪽으로 한칸 씩 옮기고 가장 오른쪽 자리에 0을 추가하는 것이고, +1 을 하는 경우에는 이진수 가장 오른쪽 자리를 1 올리는 것이다.

 

따라서 +1 한 횟수는 이진수의 1의 개수이고 *2 한 횟수는 이진수 길이 -1 이다.

 

전체 연산의 수는 +1 한 횟수 총합 + *2 한 횟수의 최댓값이다.

 

코드

import java.io.*;
import java.util.*;

public class BOJ_12931 {
    static int answer, maxMultiply;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++) {
            findAnswer(Integer.parseInt(st.nextToken()));
        }
        answer += maxMultiply;

        System.out.println(answer);

    }

    static void findAnswer(int num) {
        String binaryString = Integer.toBinaryString(num);
        int bitCount = Integer.bitCount(num);
        maxMultiply = Math.max(maxMultiply, binaryString.length() - 1);
        answer += bitCount;
    }
}

 

 

새로 알게 된 것

• Integer.toBinaryString : 10진수를 2진수 string으로 변환하는 함수이다. Integer.parseInt() 의 반대 역할
• Integer.bitCount : 이진수에서 1의 개수, 즉 true 값을 세어주는 함수이다.

 

진짜 기가막힌 함수들이다. 노가다로 다 개수 개산할뻔한걸 한번에 해결해주는 함수가 있다는걸 처음 알았다.

그리고 어떻게 이걸 보고 이진수 비트 연산으로 생각할 수 있을까? 더 많은 연습을 해야겠다.....!