C - [백준 14888] 연산자 끼워넣기 (feat. 백트래킹 + DFS)

참조 포스트

 

2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열)

C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열)

2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 9663] N-Queen (feat. 백트래킹, DFS)

C - [백준 9663] N-Queen (feat. 백트래킹, DFS)

---

 

 

https://www.acmicpc.net/problem/14888

BOJ 14888 - 연산자 끼워넣기

 

"연산자 끼워넣기" 문제는 주어진 숫자와 연산자를 이용해 가능한 모든 계산 결과를 탐색하고, 최댓값과 최솟값을 구하는 문제입니다. 연산자의 순서를 바꿔가며 계산을 수행해야 하므로 백트래킹(Backtracking) 기법을 활용하는 것이 핵심입니다.

문제의 주요 규칙은 다음과 같습니다:

1. 연산자는 +, -, *, / 네 종류입니다.
2. 연산은 연산자 우선순위를 무시하고 순서대로 진행합니다.
3. 나눗셈의 경우, 양수는 몫만 취하며, 음수는 C++14 기준에 따라 -(-a / b) 방식으로 계산합니다.

---

Checkpoint

1. 모든 가능한 연산자 순서 탐색

이 문제는 가능한 모든 연산자 조합을 확인해야 하므로, 백트래킹을 사용하여 연산자 순서를 구성하고 계산합니다.
연산자는 최대 10개까지 주어질 수 있으며, 총 가능한 조합의 수는 N-1개의 연산자의 순열입니다.

2. 연산자의 개수 관리

• 연산자는 각 종류별로 몇 개가 사용 가능한지 입력으로 주어집니다.
• 이를 관리하기 위해 operators[] 배열을 사용하며, 각 인덱스는 +, -, *, / 연산자의 남은 개수를 나타냅니다.
• DFS(Depth-First Search) 과정에서 연산자를 선택하면 개수를 줄이고, 탐색이 끝나면 다시 복구합니다.

그 전에 학습했던 문제(N-queen, N과 M 등)은 visited 배열에 토글 역할을 부여해 방문 여부를 확인하면서 백트래킹을 구현했다면, 해당 문제는 visited 배열 없이 연산자의 갯수를 감소시켰다가 백트래킹시 다시 증감시키면서 백트래킹을 구현합니다. 즉, 노드 계층(level)간의 이동(백트래킹)을 연산자의 갯수를 통해 조절합니다.

 

처음에 알고리즘을 설계할 때 연산자를 배열로 나열한 후, visited 배열을 통해 전과 같은 방식으로 설계하였습니다.

이렇게 설계하면 특정 연산자가 2개 이상일 경우 중복 처리된다는 비효율성에 문제가 있고 모든 경우의 수를 따지기가 어려워 진다는 단점이 있습니다. 그럼에도 그전에 있는 알고리즘을 우선 구현하는게 편하다고 생각하여 해당 방법으로 설계하였습니다. 그 결과, 백준에 있는 예제는 통과하지만 재출 시 오답이 계속 떠서 visited를 없애는 방법으로 설계하게 되었습니다.

 

설계단계서 부터 해당 이슈를 인지하고 있었으나 그대로 진행한 것이 패착이라고 볼 수 있습니다.

visited 배열 없이 백트래킹을 처리하는 것에 대한 연습을 더 진행할 생각입니다.

3. 나눗셈의 특별 처리

• 문제에서 음수 나눗셈은 C++14 규칙에 따라 -(-a / b) 형태로 처리해야 합니다.
• 이를 코드에서 조건문으로 구현하여 처리합니다.

---

구현 코드

#include <stdio.h>

int N; // 숫자 개수
int numbers[11]; // 숫자 배열
int operators[4]; // +, -, *, / 연산자의 개수
int MAX = -1000000000; // 최댓값 초기화
int MIN = 1000000000;  // 최솟값 초기화

// DFS 탐색 함수
void dfs(int depth, int result) {
    if (depth == N) {
        // 모든 연산을 끝낸 경우 결과 갱신
        if (result > MAX) MAX = result;
        if (result < MIN) MIN = result;
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (operators[i] > 0) {
            operators[i]--; // 연산자 사용
            int next_result = result;

            // 연산 수행
            if (i == 0) next_result += numbers[depth];          // 덧셈
            else if (i == 1) next_result -= numbers[depth];     // 뺄셈
            else if (i == 2) next_result *= numbers[depth];     // 곱셈
            else if (i == 3) {                                  // 나눗셈
                if (next_result < 0) 
                    next_result = -(-next_result / numbers[depth]);
                else 
                    next_result /= numbers[depth];
            }

            dfs(depth + 1, next_result); // 다음 단계로 이동
            operators[i]++; // 연산자 복구
        }
    }
}

int main() {
    // 입력 처리
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &numbers[i]);
    }

    for (int i = 0; i < 4; i++) {
        scanf("%d", &operators[i]); // 각 연산자의 개수
    }

    dfs(1, numbers[0]); // 첫 번째 숫자를 기준으로 DFS 시작

    // 결과 출력
    printf("%d\n", MAX);
    printf("%d\n", MIN);

    return 0;
}

---

코드 설명

1. 입력 처리

scanf("%d", &N);
for (int i = 0; i < N; i++) {
    scanf("%d", &numbers[i]);
}

for (int i = 0; i < 4; i++) {
    scanf("%d", &operators[i]); // 각 연산자의 개수
}

• N: 숫자의 개수를 입력받습니다.
• numbers[]: 계산에 사용할 숫자 배열입니다.
• operators[]: +, -, *, / 연산자의 개수를 입력받습니다.

입력 예시

6
1 2 3 4 5 6
2 1 1 1

---

2. DFS(백트래킹) 함수

void dfs(int depth, int result) {
    if (depth == N) {
        // 모든 연산을 끝낸 경우 결과 갱신
        if (result > MAX) MAX = result;
        if (result < MIN) MIN = result;
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (operators[i] > 0) {
            operators[i]--; // 연산자 사용
            int next_result = result;

            // 연산 수행
            if (i == 0) next_result += numbers[depth];          // 덧셈
            else if (i == 1) next_result -= numbers[depth];     // 뺄셈
            else if (i == 2) next_result *= numbers[depth];     // 곱셈
            else if (i == 3) {                                  // 나눗셈
                if (next_result < 0) 
                    next_result = -(-next_result / numbers[depth]);
                else 
                    next_result /= numbers[depth];
            }

            dfs(depth + 1, next_result); // 다음 단계로 이동
            operators[i]++; // 연산자 복구
        }
    }
}

핵심 동작

1. 기저 조건:
   • depth == N일 때 탐색 종료.
   • 현재 결과(result)를 MAX와 MIN과 비교하여 갱신합니다.
2. 백트래킹:
   • 현재 가능한 연산자를 하나씩 선택하여 다음 단계로 이동.
   • 재귀 호출이 끝나면 선택한 연산자를 복구(operators[i]++)합니다.
3. 나눗셈 처리:
   • 양수는 result / number로 몫만 계산.
   • 음수는 C++14 규칙에 따라 -(-result / number)로 처리.

---

3. 결과 출력

printf("%d\n", MAX);
printf("%d\n", MIN);

• 모든 경우의 수를 탐색한 후, 최댓값(MAX)과 최솟값(MIN)을 출력합니다.

---

동작 과정

입력

6
1 2 3 4 5 6
2 1 1 1

탐색 과정

1. 연산자 조합:
   • 가능한 모든 연산자의 순서를 생성합니다.
   • 예: + + - * /, + - + * /, - + / * +, ...
2. 계산:
   • 각 조합에 따라 계산을 수행합니다.
   • 예:
     • ((1 + 2) + 3) - 4 * 5 / 6
     • ((1 + 2) - 3) + 4 * 5 / 6
     • ...
3. 최대값 및 최소값 갱신:
   • 모든 조합을 계산하며, 결과를 비교해 MAX와 MIN을 갱신합니다.

---

시간 복잡도

• 숫자 개수 N에 대해 최대 (N-1)!의 경우의 수를 탐색합니다.
• 따라서 시간 복잡도는 **O((N-1)!)**입니다.
• 하지만, 문제에서 N ≤ 10이므로 계산량은 충분히 감당할 수 있습니다.

---

출력 예시

입력

6
1 2 3 4 5 6
2 1 1 1

출력

54
-24

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.