[Java] 백준알고리즘 #8741 이진수 합

백준알고리즘 #8741 이진수 합

k자리수 이하의 모든 자연수의 합을 구하는 문제이다.

예를들어 3인 경우 3자리 이하의 이진수는 111(7), 110(6), 101 (5) , 100 (4) , 11 (3) , 10 (2) , 1 (1) 와 같다.

이 수를 모두 더하면 (1+2+3+4+5+6+7) 28이 되므로 이를 다시 이진수로 나타내면 11100 이 된다.

 

수의 범위가 10만자리까지 해당되므로 결과값으로 상당히 큰 수가 나올 수 있다.

이진법으로 나타낼 때 31자리에 해당하는 값만 해도 21억(int형 최대값) 이므로 정수형으로 수를 표현하기에는 턱없이 부족하다.

 

정수형에 담아 메모리초과가 나는 예시

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String a = "";
        for (int i = 0; i < k; i++) {
            a = a + "1";
        }
        int b = Integer.parseInt(a, 2);
        int sum = (b * (b + 1)) / 2;
        System.out.println(Integer.toBinaryString(sum));
        sc.close();
    }
}

 

때문에 규칙을 찾아 문자형으로 추가해보도록 하자.

먼저 1인경우는 그대로 1이 출력된다

2인 경우 => 11 10 1 이므로 1+2+3 = 6 이 되고 이를 2진수로 나타내면 110이 된다.

3인 경우 => 예시와 같이 11100

4인 경우 => 1111이 15이므로 1~15의 값을 더하면 120이 되고 이를 이진수로 나타내면 1111000이 된다.

 

즉 k인 경우 1이 k개 0이 k-1개 나타나는 규칙을 확인할 수 있다.

이제 코드를 작성해보자.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String a = "";
        for (int i = 0; i < k; i++) {
            a = a + "1";
        }
        for (int i = 0; i < k - 1; i++) {
            a = a + "0";
        }

        System.out.println(a);
        sc.close();
    }
}

k개만큼의 1과 k-1개 만큼의 0을 출력하는 코드를 작성했다.

그러나 결과는 메모리 초과. 루프를 많이 돌면서 문자열을 추가하는 것이 메모리를 많이 잡아먹어서 실패 판정이 났다.

이를 해결하기 위해 찾아보니 단순 반복함수인 repeat() 메소드가 있는것을 확인. 이를 사용해보도록 하자.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String sum = "1".repeat(k) + "0".repeat(k - 1);
        System.out.println(sum);
        sc.close();
    }
}

repeat()메소드는 앞에오는 문자열을 파라미터 값 만큼 반복하는 메소드이다.

이를 이용해 제출하였더니 성공!