[백준 자바] 2226번(이진수)

난이도 - 골드 4

문제

0과 1로 구성된 이진수가 있다. 이 이진수에서 0을 10으로, 1을 01로 동시에 치환하면 길이가 두 배인 이진수를 얻을 수 있다. 이러한 이진수들을 차례로 나열하면 하나의 이진수 수열이 된다. 편의상 시작 수는 1이라고 하자. 처음 몇 개의 이진수들을 구해 보면,

1 → 01 → 1001 → 01101001 → …

이 된다.

N이 주어졌을 때, N번째 이진수에서 연속된 0들의 그룹이 몇 개나 있는지 알아내는 프로그램을 작성하시오. N=4일 경우의 이진수는 01101001이고, 따라서 이 안에는 연속된 0들이 세 그룹 있게 된다.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 답을 출력한다.

 

---

 

728x90

2진수를 나열하고 0의 그룹 개수를 찾는 코드를 작성하면 메모리 초과가 뜬다. 규칙을 찾으면 쉽게 풀 수 있다.

N	2진수	0 그룹 개수
1	1	0
2	01	1 (0*2+1)
3	1001	1 (1*2-1)
4	01101001	3 (1*2+1)
5	1001011001101001	5 (3*2-1)
6	...	11 (5*2+1)
7	...	21 (11*2-1)

N이 짝수일때 0 그룹 개수는 N-1번째 0 그룹 개수 * 2 +1이고,

N이 홀수일때 0 그룹 개수는 N-1번째 0 그룹 개수 * 2 -1이다.

import java.io.*;
import java.math.BigInteger;

public class Main2226 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

    bw.write(String.valueOf(zeroGroup(N)));

    bw.flush();
    br.close();
    bw.close();
  }

  static BigInteger zeroGroup(int n) {
    int i = 1;
    BigInteger count = BigInteger.ZERO;

    while (i < n) {
      if (i % 2 == 1)
        count = count.multiply(BigInteger.TWO).add(BigInteger.ONE);
      else
        count = count.multiply(BigInteger.TWO).subtract(BigInteger.ONE);
      i++;
    }

    return count;
  }
}