[백준 - 2248번] 이진수 찾기 - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp
N(1 ≤ N ≤ 31)자리의 이진수가 있다. 이러한 이진수 중에서, L(1 ≤ L ≤ N)개 이하의 비트만 1인 것을 크기 순으로 나열했을 때, I번째로 나오는 이진수를 구해내는 프로그램을 작성하시오. 이진수는 0으로 시작할 수도 있다.

입력

첫째 줄에 세 정수 N, L, I가 주어진다. I번째 이진수가 있는 입력만 주어진다.

출력

첫째 줄에 답을 출력한다.

풀이

2^31은 21억을 넘기기 때문에 모든 이진수를 구하는 것은 불가능하다.

그래서 2차원 dp를 사용해야 한다.

dp[A][B]
여기서 A는 길이이고, B는 1의 개수다.

그래서 dp[2][1]은 길이가 2이면서 1의 개수가 1인 값이 된다.

점화식을 구해보면,
dp[3][2] = dp[2][2] + dp[2][1]이 된다.

왜냐하면 길이가 3일 때 1이 두 개인 경우는

• 길이가 2일 때 1이 두 개인 경우
• 길이가 2일 때 1이 하나인 경우와 가장 앞에 1인 형태
  를 합한 경우이기 때문이다.

그리고 나서, 각 dp 길이마다 합을 구해야 한다.
ex)
dp[3][3] -> dp[3][3] + dp[3][2] + dp[3][1] + dp[3][0];
dp[3][2] -> dp[3][2] + dp[3][1] + dp[3][0];
..

합해주는 이유는 길이가 3이면서 1이 3개일 때 모든 경우의 수를 구하기 위함이다.

이 값을 길이마다 구하면 특정 자리에 비트를 구할 수 있다.

예를 들어 길이가 3이면서 1이 2개일 때 값이 3이라면 (sumDp[3][2])
3보다 크다는 것은 4번 째 자리가 1이고, 작거나 같다면 0이라는 것이다. (전체 길이가 4라고 한다면)

그래서 이런 식으로 4번 째 자리부터 1번 째 자리까지 비트를 구해주면 되는데 만약 앞에 비트가 1인 경우가 나온다면 L-=1을 하고, L개 이하까지의 합을 이용해야 한다. (반복되는 구조)

그리고 처음에는 5번 째를 구하다가도 1이 나오는 순간 5 -= 합(sumDp[3][2])을 해서 업데이트 해줘야 한다.

왜냐하면 앞에 1이 나왔기 때문에 그 자리가 제외된 상태로 구하기 때문이다.
ex)
...
0xx
0xx -> 여기까지의 합이 더 크기 때문에 앞의 1이 붙음 그러면 다음 I는 1xx에서 xx이기 때문에 여기까지의 합을 빼줘야 됨
1xx
1xx
1xx

이런 식으로 코드를 구현해 주면 답을 구할 수 있다.

이 풀이의 시간 복잡도는 O(N * L)이다.

소스 코드

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

public class Main {
    static int N, L;
    static long I;
  public static void main(String args[]) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      L = Integer.parseInt(st.nextToken());
      I = Long.parseLong(st.nextToken());
      
      long[][] dp = new long[N][L + 1]; //N - 1까지만 구하면 됨 어차피 I번째 이진수가 있는 입력만 주어지기 때문
      
      for(int i=1; i<=N - 1; i++) {
          dp[i][0] = 1;
          dp[i][1] = i;
      }
      
      for(int i=2; i<=N - 1; i++) {
          for(int j=2; j<=L; j++) {
              if(i < j) {
                  break;
              }
              dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
          }
      }
      
      for(int i=1; i<= N - 1; i++) {
          for(int j=1; j<=L; j++) {
              dp[i][j] += dp[i][j - 1];
          }
      }
      
      //N자리 수의 비트를 결정해야 됨
      StringBuilder sb = new StringBuilder();
      for(int i=N; i>=1; i--) {
          long std = i - 1 == 0 ? 1 : dp[i - 1][L];
          if(I > std) {
              sb.append(1);
              L -= 1;
              I -= std;
          } else {
              sb.append(0);
          }
      }
      System.out.println(sb.toString());
  }
}