[Jungol] 정올 1180 Dessert

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=463&sca=9040

 Input 
7

 Output 

1 + 2 - 3 + 4 - 5 - 6 + 7

1 + 2 - 3 - 4 + 5 + 6 - 7

1 - 2 + 3 + 4 - 5 + 6 - 7

1 - 2 - 3 - 4 - 5 + 6 + 7

1 - 2 . 3 + 4 + 5 + 6 + 7

1 - 2 . 3 - 4 . 5 + 6 . 7

6

 

사전순으로 최대 20개까지 출력하는 것이므로, 1 ~ 20까지의 숫자 순서는 변화가 없습니다.

문제에서 주어진 연산도 "+", "-", "." 순으로 우선순위를 가집니다.

→ 수와 수 사이에 연산자의 개수는 N - 1 개 입니다.

→ 가능한 경우의 수는 3N-1 에 해당합니다.

    N은 최대 15 이므로 314 = 4,782,969 → 따라서 TLE 문제는 발생하지 않습니다.

→ 만들 수 있는 가장 큰 수는 모든 숫자에  「 . 」이 들어간 형태 입니다.

    1 ~ 15 → 123456789101112131415이지만, 문제에서 요구하는 것은 결과 = 0 입니다.

    따라서 12345678910 이상의 수를 만들게 된다면 어떤 연산이 적용되어도 최종 결과는 0을 만들 수 없기 때문에

    적절한 가지치기(pruning)이 가능합니다.

    ex) A = 12345678910일 때, 나머지 수 B는 최대 1112131415인데 A - B ≠ 0

    즉, DFS 진행하다가 A or B 중에서 특정 수치(INF)를 넘어서면 더 이상 진행할 필요가 없습니다.

→ +, - 연산은 두 수의 연산결과를 인자로 전달하면 DFS 탐색하면 되지만

    . 연산을 위해서는 추가적인 설계가 필요합니다.

    ex) 4 + 5 . 6 = 4 + 56 = 60 → 연산 자체는 + 연산 보다는 . 연산이 먼저 처리되어야 합니다.

          마치 +, - 연산 보다 우선시 되는 ×, ÷ 연산이 적용되었다고 보면 됩니다.

          물론 일반적으로 접근하는 Stack을 이용해서 구현할 수 있지만 두 개 변수를 이용해서 구현가능합니다.

 

DFS(depth, A, B)

    - A = 직전에 등장한 +, - 이전까지의 결과

    - B = 직전에 등장한 +, - 이후부터 0개 이상의 .(점)을 계산하여 하나의 수로 만든 결과

새로운 +,- 가 나오면 A에 B를 더하고 B는 새로운 값으로 시작합니다.

( 「-」 연산자는 음수로 만들어서 인자를 전달하기에 더하기만 해줍니다.)

 

「. 」 숫자가 10의 자리 수 미만일 때는 10 단위로 곱해져 숫자가 붙지만,

10의 자리 이상 부터는 100 단위로 곱해져 숫자가 붙습니다.

▶ 1은 무조건 사용되므로 DFS(2, 0, 1)로 구현 (A = 0, B = 1)

---

#include <stdio.h>
typedef long long LL;
inline LL abs(LL k) { return k < 0 ? -k : k; }
const LL INF = 12345678910LL;
const int LM = 20;
 
int N, op[LM], cnt;
 
void output() {
    printf("1 ");
    for (int i = 2; i <= N; ++i) {
        printf("%c %d ", op[i], i);
    }
    puts("");
}
 
void DFS(int depth, LL A, LL B) {
    // pruning
    if (abs(A) >= INF || abs(B) >= INF) return;
 
    if (depth > N) {
        if (A + B == 0) {
            cnt++;
            // 20개까지 출력한 경우
            if (cnt > 20) return;
            output();
        }
        return;
    }
 
    op[depth] = '+';
    DFS(depth + 1, A + B, depth);
    op[depth] = '-';
    DFS(depth + 1, A + B, -depth);
 
    op[depth] = '.'; 
    int base = depth < 10 ? 10 : 100, t = depth;
    if (B < 0) t = -t;
    DFS(depth + 1, A, B * base + t);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    DFS(2, 0, 1);
    printf("%d\n", cnt);
}