와 이문제 너무 어려워요. 다들 도대체 어떻게 푼거죠,,? 하루를 고민하다가 결국 다른 사람의 풀이방법을 조금 본 문제입니다 ㅠ.....

문제링크

백준 #2248. 이진수 찾기

풀이방법

문제를 크게 두 부분으로 나눠볼게요.
#1. dp[n][k]: n개 bit 중, k개의 bit 1을 갖는 경우의 수 <- 이 의미의 테이블을 채우는 단계
#2. l개의 이하의 bit 1을 갖는 수 중 i번째 수 찾기

#1

이 단계는 쉬워요. 평소에 동적프로그래밍 문제를 풀듯, 점화식을 찾으면 됩니다.

dp[n][k] = dp[n-1][k-1] + dp[n-1][k]
(n개 bit 중, k개의 bit 1을 갖는 경우) = (dp[n-1][k-1]에 bit 1 추가) + (dp[n-1][k]에 bit 0 추가)

이 점화식 자체는 쉽게 추론할 수 있지만 (dp[n-1][k-1]에 bit 1 추가), (dp[n-1][k]에 bit 0 추가) 이 두 케이스의 크기 비교가 두번째 단계에서 중요한 역할을 합니다!

추가하는 비트를 가장 앞에 오도록 한다고 생각합시다.
(dp[n-1][k-1]에 bit 1 추가)의 크기가 (dp[n-1][k]에 bit 0 추가)의 크기보다 클 수 밖에 없겠죠??? 전자가 모두 bit 0으로만 채워져 있어도 2^(n-1)이 되는데 후자는 모두 bit 1로 채워져 있어도 2^(n-1) - 1이 되기 때문에 이해에 어려움은 없을거라 생각합니다. 이를 잊지말고 두번째 단계로 갑니다!

#2

순서를 바탕으로 역추적하는 느낌으로 진행되는 단계에요.

dp[n] -> dp[1] 으로 이동하며 각 자리에 맞는 비트를 찾을겁니다.

지금 자리(k)에 비트 0이 오는지 1이 오는지는 그 전 자리 정보를 이용합니다. dp[k - 1][0] ~ dp[k - 1][l] 값을 더하고 i와 비교합니다. 더한 값을 sum이라고 칭하겠습니다. 이 sum을 기준으로 앞에 1을 붙이냐 0을 붙이냐를 결정할 수 있습니다.

• i > sum
  앞에 비트 1이 붙는 경우입니다. sum은 앞에 비트 0을 붙인 경우의 수라고 생각할 수 있는데 그 수보다 크기 때문에 비트 1을 붙여 순서상 더 뒤에 위치하는 수를 찾고있다고 생각할 수 있죠! 이 경우엔 비트 1을 찾았기 때문에 남은 비트 1의 수를 의미하는 l 값을 하나 빼줍니다. 또, 비트 0을 붙인 경우들을 걸러냈기 때문에 i - sum을 해줍니다.
• i <= sum
  앞에 비트 0이 붙는 경우입니다. 걸러낼 것도 없고 비트 1도 찾지 못했죠. 따라서 변수에는 변화가 없습니다.

이 컨셉을 유지하며 dp[1]까지 이동하면 답을 얻을 수 있습니다!

코드

import java.util.Scanner;
import java.util.stream.IntStream;

public class BinaryNumber {
    static long[][] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 1 <= n <= 31
        int l = sc.nextInt();
        long i = sc.nextLong(); // n의 범위때문에 최대 2^31(int범위 초과)

        dp = new long[n + 1][l + 1];
        dp[0][0] = 1;

        for (int y = 1; y <= n; y++) {
            dp[y][0] = 1;
            for (int x = 1; x <= l; x++) {
                dp[y][x] = dp[y - 1][x - 1] + dp[y - 1][x]; // 1 bit를 추가하는 경우 / 0 bit를 추가하는 경우
            }
        }

        StringBuilder result = new StringBuilder();
        for (int pos = n; pos > 0; --pos) {
            final int tempPos = pos;
            long count = IntStream.range(0, l + 1). // count할 범위를 현재 남은 1 bit 수로 설정해야지 !!!
                    mapToLong(k -> dp[tempPos - 1][k]).
                    sum();

            int digit;
            if (count < i) {
                digit = 1;
                i -= count;
                l--;
            } else digit = 0;

            result.append(digit);
        }

        System.out.print(result.toString());
    }
}

🤯🤯

어려운 문제였어요,,,,