[DP] ‘K번째 찾기’와 카운팅 DP (백준 1256)

목차

• 1. 서론: 우주의 원자보다 많은 문자열
• 2. [시행착오 1] 무식하게 다 적어보기 (Backtracking)
• 3. [시행착오 2] 스마트하게 적어보기? (List DP)
• 4. [Deep Dive] 점화식은 어떻게 탄생했는가?
• 5. 해결책: 이름 대신 인원수만 세자 (Counting DP)
• 6. 결정적 로직: 건너뛰기 (Skip Strategy)
• 7. 최종 코드 및 구현 공식

1. 서론: 우주의 원자보다 많은 문자열

개발자가 알고리즘 문제를 풀 때 가장 범하기 쉬운 실수 중 하나는 “컴퓨터는 빠르니까 다 해보면 되겠지”라는 안일한 생각입니다. 백준 1256번 ‘사전’ 문제가 바로 그 안일함을 처절하게 응징하는 문제입니다.

문제는 간단해 보입니다. ‘a’가 N개, ‘z’가 M개 있는 문자열 중 사전 순으로 K번째인 것을 찾으라고 합니다. 하지만 N과 M이 최대 100이라는 조건을 보는 순간, 숙련된 개발자는 등골이 서늘해져야 합니다. 조합 공식에 따르면, N=100, M=100일 때 가능한 문자열의 개수는 약 9.05 × 10⁵⁸개입니다. 우리가 관측 가능한 우주의 원자 개수가 약 10⁸⁰개인 것을 감안하면, 이는 실로 천문학적인 숫자입니다.

이 거대한 탐색 공간에서 우리는 어떻게 1초 안에 K번째 문자열을 핀셋처럼 집어낼 수 있을까요? 두 번의 실패한 시도(시행착오)를 통해 그 해답을 찾아보겠습니다.

2. [시행착오 1] 무식하게 다 적어보기 (Backtracking)

첫 번째 접근은 가장 직관적인 백트래킹(Backtracking)입니다. 재귀 함수를 이용해 ‘a’와 ‘z’를 하나씩 붙여가며 트리를 타고 내려가는 방식입니다. 모든 문자열을 완성한 뒤 리스트에 담아 list.get(K-1)을 하겠다는 전략입니다.

실패한 코드 분석 (전체 코드)

import java.util.*;

// [시도 1] 백트래킹을 이용한 전수 조사
// 결과: 메모리 초과 (Memory Limit Exceeded)
class Main {
    static int n, m, k;
    static List<String> res; // 치명적 원인: 모든 결과를 저장하려 함
    static char[] tmp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        init(n, m);
        run(0);
        
        // K번째가 존재하지 않는 경우의 예외처리도 미흡함
        if (res.size() < k) System.out.println("-1");
        else System.out.println(res.get(k - 1));
    }

    static void init(int n, int m) {
        res = new ArrayList<>();
        tmp = new char[n + m];
    }

    static void run(int lv) {
        // 기저 사례: 문자열 완성 시 리스트에 추가
        if (lv == tmp.length) {
            res.add(new String(tmp)); 
            return;
        }
        
        // 'a'를 먼저 선택 (사전 순)
        if (n > 0) {
            tmp[lv] = 'a';
            n--;
            run(lv + 1);
            n++; // 백트래킹 (원상복구)
        }
        
        // 그 다음 'z'를 선택
        if (m > 0) {
            tmp[lv] = 'z';
            m--;
            run(lv + 1);
            m++;
        }
    }
}

기술적 분석: 왜 실패했는가?

이 코드는 조합의 폭발(Combinatorial Explosion)을 정면으로 맞이합니다. N, M이 20 정도만 되어도 리스트의 크기는 수천만 건을 넘어가며, 각 항목이 String 객체이므로 JVM의 Heap 메모리가 순식간에 고갈됩니다. “찾고자 하는 것만 찾아야지, 전부 다 만들면 안 된다”는 교훈을 얻을 수 있습니다.

3. [시행착오 2] 스마트하게 적어보기? (List DP)

백트래킹의 중복 연산을 줄이기 위해 메모이제이션(DP)을 도입한 두 번째 시도입니다. 점화식은 완벽했습니다. dp[i][j]는 dp[i-1][j](앞에 a를 붙인 것)와 dp[i][j-1](앞에 z를 붙인 것)의 합집합이라는 논리입니다.

실패한 코드 분석 (전체 코드)

import java.util.*;

// [시도 2] 2차원 DP에 List<String> 저장
// 결과: 메모리 초과 (Memory Limit Exceeded)
class Main {
    static int n, m, k;

    public static String solution() {
        // [치명적 실수] DP 테이블의 각 칸에 거대한 리스트를 담으려 함
        List<String>[][] dp = new ArrayList[n + 1][m + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = new ArrayList<>();
                
                // 초기값: 한 종류의 문자만 남은 경우
                if (i == 0 && j > 0) dp[0][j].add("z".repeat(j));
                if (j == 0 && i > 0) dp[i][0].add("a".repeat(i));
            }
        }

        // 점화식 적용
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 위쪽 칸(i-1, j)의 모든 문자열 앞에 'a'를 붙여서 저장
                for (String s : dp[i - 1][j]) {
                    dp[i][j].add("a" + s);
                    // (메모리 폭발 지점: 문자열 객체가 기하급수적으로 복제됨)
                }
                // 왼쪽 칸(i, j-1)의 모든 문자열 앞에 'z'를 붙여서 저장
                for (String s : dp[i][j - 1]) {
                    dp[i][j].add("z" + s);
                }
            }
        }

        if (dp[n][m].size() < k) return "";
        return dp[n][m].get(k - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        String ans = solution();
        if (ans.equals("")) System.out.println(-1);
        else System.out.println(ans);
    }
}

기술적 분석: 자료구조의 오판

이 시도는 논리는 맞았으나 도구가 틀린 경우입니다. 점화식 자체는 정확했지만, DP 테이블의 각 셀(Cell)에 List<String>이라는 무거운 객체를 담으려 했습니다. 문자열이 합쳐질 때마다 새로운 객체가 생성되고, 메모리 사용량은 여전히 기하급수적으로 늘어납니다.

4. [Deep Dive] 점화식은 어떻게 탄생했는가?

앞선 [시도 2]에서 사용된 점화식 dp[i][j] = dp[i-1][j] + dp[i][j-1]은 단순히 외워서 쓰는 공식이 아닙니다. 이는 문제의 구조를 '첫 글자' 기준으로 분해했을 때 자연스럽게 도출되는 결과입니다.

논리적 유도 과정

'a'가 i개, 'z'가 j개 있는 상황에서 문자열을 만든다면, 가장 먼저 해야 할 일은 맨 앞에 올 글자를 고르는 것입니다. 선택지는 단 두 가지뿐입니다.

• Case A: 맨 앞에 'a'가 오는 경우

  첫 자리에 'a'를 놓았습니다. 이제 남은 재료는 'a'가 i-1개, 'z'가 j개입니다. 이 남은 재료들로 만들 수 있는 모든 경우의 수가 바로 dp[i-1][j]입니다.

• Case B: 맨 앞에 'z'가 오는 경우

  첫 자리에 'z'를 놓았습니다. 이제 남은 재료는 'a'가 i개, 'z'가 j-1개입니다. 이 남은 재료들로 만들 수 있는 모든 경우의 수가 바로 dp[i][j-1]입니다.

결론: 합의 법칙

어떤 문자열이 동시에 'a'로 시작하면서 'z'로 시작할 수는 없습니다(배반 사건). 따라서 전체 경우의 수는 이 두 케이스를 더한 값과 같습니다. 이 논리가 바로 파스칼의 삼각형이며, 카운팅 DP의 근간이 됩니다.

5. 해결책: 이름 대신 인원수만 세자 (Counting DP)

이제 우리는 두 번의 실패를 통해 확실한 결론에 도달했습니다. "문자열 자체를 메모리에 올리면 죽는다."

해결책은 추상화(Abstraction)입니다. 구체적인 문자열("aaaz", "aaza"...) 대신, 그 집합의 크기(개수)만 저장하는 것입니다.

• 변경 전: List<String>[][] dp → 리스트 내용: ["aaaz", "aaza", "azza"]
• 변경 후: int[][] dp → 값: 3

이렇게 자료형을 int로 바꾸는 순간, 메모리 사용량은 기하급수적 그래프에서 선형 그래프로 급격히 줄어듭니다. 이것이 바로 카운팅 DP(Counting DP)의 핵심입니다.

6. 결정적 로직: 건너뛰기 (Skip Strategy)

개수를 다 세어두었다면, 정작 K번째 문자열이 무엇인지는 어떻게 알 수 있을까요? 여기서 '사전 찾기'의 비유가 등장합니다. 우리가 사전을 펼칠 때 1페이지부터 읽지 않고, 찾는 단어의 첫 글자를 보고 페이지 뭉텅이를 건너뛰는 것과 같은 원리입니다.

핵심 알고리즘: 분할 정복 (Divide and Conquer)

현재 상태(a가 N개, z가 M개)에서 첫 글자를 결정하는 로직입니다.

1. 질문: "만약 내가 첫 글자로 'a'를 선택한다면, 그 뒤에 만들어질 수 있는 문자열은 총 몇 개인가?" (count = dp[N-1][M])
2. 비교 및 결정:
   • Case A (K ≤ count): "찾는 순서가 이 개수 안에 포함된다."
     → 정답은 'a'로 시작함이 확실하다.
     → 결과에 'a'를 추가하고, N을 하나 줄여서 계속 탐색한다.
   • Case B (K > count): "찾는 순서가 이 개수를 넘어선다."
     → 정답은 'a'로 시작하는 그룹에는 없다. 'a' 그룹을 전부 건너뛴다(Skip).
     → 결과에 'z'를 추가하고, M을 하나 줄인다.
     → 중요: 앞서 건너뛴 'a' 그룹의 개수만큼 K값을 줄인다. (K = K - count)

7. 최종 코드 및 구현 공식

수많은 시행착오 끝에 완성된 최종 코드입니다. List 대신 int[][]를 사용하고, StringBuilder와 static 변수를 활용해 메모리와 속도를 극한으로 최적화했습니다.

import java.util.*;

public class Main {
    static int N, M, K;
    static int[][] dp;
    static StringBuilder sb = new StringBuilder();
    static final int MAX_K = 1_000_000_000; // K의 최댓값 (10억)

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();

        // 1. DP로 조합 개수 구하기 (카운팅)
        dp = new int[N + 1][M + 1];
        
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1; // 한 종류만 남으면 경우의 수는 1
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    // [핵심] 오버플로우 방지: K 범위를 넘어가면 MAX_K + 1로 고정
                    if (dp[i][j] > MAX_K) dp[i][j] = MAX_K + 1;
                }
            }
        }

        // 예외 처리: 불가능한 순서인 경우
        if (dp[N][M] < K) {
            System.out.println("-1");
            return;
        }

        // 2. 분할 정복으로 문자열 생성
        query(N, M, K);
        System.out.println(sb.toString());
    }

    // 재귀적으로 한 글자씩 결정하는 함수
    static void query(int n, int m, int k) {
        // 기저 사례: 한쪽 문자가 바닥나면 나머지를 다 붙임
        if (n == 0) {
            sb.append("z".repeat(m));
            return;
        }
        if (m == 0) {
            sb.append("a".repeat(n));
            return;
        }

        // 현재 상태에서 'a'를 선택했을 때 가능한 가지 수 (사전 순이므로 a 먼저 고려)
        int countIfA = dp[n - 1][m];

        if (k <= countIfA) {
            // 찾는 순서(k)가 'a' 그룹 범위 안에 있음
            sb.append('a');
            query(n - 1, m, k); // 'a' 하나 사용, k는 그대로
        } else {
            // 찾는 순서(k)가 'a' 그룹을 벗어남 -> 'z' 확정
            sb.append('z');
            // 'a' 그룹의 개수만큼 건너뜀 (Skip Logic)
            query(n, m - 1, k - countIfA); 
        }
    }
}

결국 백준 1256번 문제는 '모든 길을 가보는 것(백트래킹)'이 아니라, '지도를 보고 갈 길만 가는 것(분할 정복)'이 핵심이었습니다. 여러분이 겪은 메모리 초과의 시행착오는 이 '지도의 필요성'을 깨닫게 해주는 아주 값진 경험이었을 것입니다.