[백준/JAVA] 8741번 이진수 합

문제

백준 8741번 이진수 합 JAVA

내 풀이 1 : 시간초과

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        long num = Long.parseLong(br.readLine());
        long index = (long)Math.pow(2, num) - 1;
        long count = 0;

        // 1. Math.pow(2, num) - 1을 구하는 것이 문제이다.
        // 2. for문을 돌려서 숫자만큼 더한다.

        for (int i = 1; i <= index; i++) {
            count += i;
        }

        // 10진수를 2진수로 변화해주는 toBinaryString메서드를 사용한다.
        String answer = Long.toBinaryString(count);

        sb.append(answer);
        System.out.println(sb.toString());
    }
}

내 풀이 2 : 시간초과

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        long num = Long.parseLong(br.readLine());
        long index = (long)Math.pow(2, num) - 1;
        long count = 0;

        // 1. Math.pow(2, num) - 1을 구하는 것이 문제이다.
        // 2. 1부터 n까지의 합을 구하는 수식을 이용한다.
        count = (index * (index + 1)) / 2;

        // 10진수를 2진수로 변화해주는 toBinaryString메서드를 사용한다.
        String answer = Long.toBinaryString(count);

        sb.append(answer);
        System.out.println(sb.toString());
    }
}

내 풀이 3 : 정답입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int i = 0; i < num; i++) {
            sb.append("1");
        }

        for (int i = 1; i < num; i++) {
            sb.append("0");
        }

        System.out.println(sb.toString());
    }
}

내 풀이 4 : 정답입니다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        // 2^k - 1 계산 (모든 자리수가 1인 이진수)
        BigInteger index = BigInteger.TWO.pow(num).subtract(BigInteger.ONE);

        // 합 계산: S = N * (N + 1) / 2
        BigInteger sum = index.multiply(index.add(BigInteger.ONE)).divide(BigInteger.TWO);

        String answer = sum.toString(2);

        sb.append(answer);
        System.out.println(sb.toString());
    }
}

느낀점

누적합을 구하는 공식을 찾고나서는 무조건 맞혔겠거니 했는데 시간초과가 떠서
뭐지??? 하고 한참 생각해도 잘 모르겠어서 검색해보니까
규칙성을 찾는 문제였다.
내 코드를 살리기 위해서는 count변수를 BigInteger로 받아야할 것 같은데
toBinaryString()메서드를 BigInteger에서 사용할 수 없었다.(메서드가 없다)
별찍기랑 다를게 뭐야!!

+) BigInteger로도 2진수로 변환할 수 있어서 코드에 적용해본 결과 정답처리를 받았다. 다만 시간이 거의 3배 가까이 차이가 난다.