백준 2248 - 이진수 찾기(Java)

🎯 문제 요약

• 길이가 N인 이진수 중에서 1의 개수가 L 이하인 이진수들을 사전 순으로 정렬했을 때, K번째 이진수를 구하는 문제.

---

🧠 문제 접근

이 문제는 모든 이진수를 직접 만들어서 K번째를 찾기에는 비효율적

핵심 아이디어는 조합을 이용해 가능한 경우의 수를 계산하며 자릿수를 결정

---

🔍 알고리즘 설계

✅ 조합 미리 계산

comb[n][k] = nCk (n개 중 k개를 고르는 경우의 수)

파스칼 삼각형을 활용하여 조합을 미리 계산합니다.

for (int i = 0; i <= 32; i++) {
    comb[i][0] = comb[i][i] = 1;
    for (int j = 1; j < i; j++) {
        comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
    }
}

✅ 자리수 별 분기

• i번째 자리를 '0'으로 채울 경우 → 나머지 자리에서 1이 L개 이하인 경우의 수 = comb[i - 1][0] + ... + comb[i - 1][L]
• 만약 이 값보다 K가 작거나 같다면 현재 자리는 '0'
• 아니라면 현재 자리는 '1', K에서 해당 경우의 수만큼 빼고, L--

---

💻 전체 코드

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

public class Main {
    static int N, L;
    static long K;
    static long[][] comb = new long[33][33];

    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()); // 1의 개수 제한
        K = Long.parseLong(st.nextToken());   // K번째 이진수

        initComb(); // 조합 테이블 초기화

        StringBuilder result = new StringBuilder();
        int onesLeft = L;
        long order = K;

        for (int i = N; i > 0; i--) {
            long zeroCount = countValid(i - 1, onesLeft); // 앞자리를 0으로 시작할 수 있는 경우의 수

            if (order <= zeroCount) {
                result.append('0');
            } else {
                result.append('1');
                order -= zeroCount;
                onesLeft--;
            }
        }

        System.out.print(result);
    }

    // 조합 계산 (nCk)
    static void initComb() {
        for (int i = 0; i <= 32; i++) {
            comb[i][0] = 1;
            comb[i][i] = 1;
        }

        for (int i = 1; i <= 32; i++) {
            for (int j = 1; j < i; j++) {
                comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
                if (comb[i][j] > 1_000_000_000) comb[i][j] = 1_000_000_000; // overflow 방지
            }
        }
    }

    // i자리 이하에서 1이 max개 이하인 이진수 개수
    static long countValid(int digit, int maxOne) {
        long sum = 0;
        for (int i = 0; i <= maxOne; i++) {
            sum += comb[digit][i];
        }
        return sum;
    }
}

---

✅ 시간복잡도

단계	복잡도
조합 계산	O(N^2)
이진수 생성	O(N)

---

💡 정리

• 단순하게 모든 경우를 만드는 것이 아니라, 조합으로 경우의 수를 세며 사전 순으로 결정해야 하는 문제
• 이진수 생성 문제에서 자주 쓰이는 대표 패턴