완전탐색 문제들은 겉보기에 단순해 보이지만, 효율적인 탐색 범위 설정과 수학적 변형이 핵심입니다. 세 가지 대표적인 문제를 통해 최적화 기법을 살펴봅니다.

문제 1: Division (UVa 725)

0~9의 각 숫자를 정확히 한 번씩 사용하여 abcde / fghij = n 형태의 식을 찾는 문제입니다.

핵심 아이디어

분자와 분모를 각각 순회하면 10¹⁰에 달하는 경우의 수가 발생합니다. 대신 등식을 abcde = n × fghij로 변형하면 분모만 순회하며 분자를 계산할 수 있어 탐색 공간이 10⁴ 수준으로 축소됩니다.

구현

#include <cstdio>
#include <cstring>

char expr[14] = {'0','0','0','0','0',' ','/',' ','0','0','0','0','0','\0'};

bool digits_unique() {
    bool seen[10] = {false};
    for (int i = 0; i < 13; i++) {
        int d = expr[i] - '0';
        if (d < 0 || d > 9) continue;
        if (seen[d]) return false;
        seen[d] = true;
    }
    return true;
}

void format_nums(int numer, int denom) {
    expr[0] = expr[8] = '0';
    int p = 4;
    while (p >= 0 && numer) {
        expr[p--] = numer % 10 + '0';
        numer /= 10;
    }
    p = 12;
    while (p >= 8 && denom) {
        expr[p--] = denom % 10 + '0';
        denom /= 10;
    }
}

int main() {
    int n;
    bool header = true;
    while (scanf("%d", &n) == 1 && n) {
        if (!header) puts("");
        header = false;
        
        int found = 0;
        for (int d = 1000; d < 100000; d++) {
            int num = d * n;
            if (num > 99999) break;
            format_nums(num, d);
            if (!digits_unique()) continue;
            printf("%s = %d\n", expr, n);
            found++;
        }
        if (!found) printf("There are no solutions for %d.\n", n);
    }
    return 0;
}

문제 2: Maximum Product (UVa 11059)

최대 연속 부분곱을 찾는 문제로, n ≤ 18이므로 O(n²) 완전탐색이 충분합니다.

주의사항

• 곱셈 결과가 int 범위를 초과할 수 있어 long long 필수
• 음수 × 음수 = 양수 케이스 고려
• 최대값이 0 이하일 경우 0 출력

구현

#include <cstdio>

int main() {
    int n, seq[20];
    int tc = 0;
    
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) scanf("%d", &seq[i]);
        
        long long best = 0;
        for (int i = 0; i < n; i++) {
            long long prod = 1;
            for (int j = i; j < n; j++) {
                prod *= seq[j];
                if (prod > best) best = prod;
            }
        }
        printf("Case #%d: The maximum product is %lld.\n\n", ++tc, best);
    }
    return 0;
}

문제 3: Fractions Again?! (UVa 10976)

1/k = 1/x + 1/y 방정식의 해를 모두 찾는 문제입니다.

수학적 최적화

방정식을 정리하면 x = ky/(y-k)가 됩니다. 이를 통해:

1. y의 하한: y > k (분모가 0이 되지 않도록)
2. y의 상한: x ≥ y 조건과 1/k = 1/x + 1/y ≤ 2/y로부터 y ≤ 2k 도출

따라서 y는 [k+1, 2k] 범위만 검사하면 됩니다.

구현

#include <cstdio>
#include <vector>

using pii = std::pair<int,int>;

int main() {
    int k;
    while (scanf("%d", &k) == 1 && k) {
        std::vector<pii> sol;
        
        for (int y = k + 1; y <= 2 * k; y++) {
            long long numer = 1LL * k * y;
            long long denom = y - k;
            if (numer % denom) continue;
            int x = numer / denom;
            sol.emplace_back(x, y);
        }
        
        printf("%zu\n", sol.size());
        for (auto &[x, y] : sol) {
            printf("1/%d = 1/%d + 1/%d\n", k, x, y);
        }
    }
    return 0;
}

요약