[BOJ/백준] 15658 연산자 끼워넣기 (2)

● [문제번호 15658] 연산자 끼워넣기 (2)

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

15658번: 연산자 끼워넣기 (2)

 

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

: 재귀

 

 

● 풀이 과정

: 14888 연산자 끼워넣기 문제에서

연산자의 총 갯수가 N-1보다 크거나 같고, 4N보다 작거나 같다는 조건이 추가된다.

 

그런데 조금 생각해보니

14888 연산자 끼워넣기 문제를 풀 때 이러한 경우까지 커버할 수 있게 구현되어서

똑같은 코드로도 통과할 수 있었다.

 

: [521 - 브루트 포스 - 순열(연습)] 문제집에 있는 문제

 

: 어떻게 모든 경우의 수를 탐색할까 하다가

주어진 수의 순서를 바꾸면 안된다. 라는 말을 고려하여

수를 나열해놓고 사이사이에 사칙연산을 하나씩 대입하며 재귀하는 방법으로 구현했다.

 

: 맨 처음 숫자만 total에 더하고

그 다음 숫자부터는 사칙연산에 따라 계산을 하여 total에 저장한다.

 

1. 덧셈인 경우

추가 → 재귀 → 제거

 

2. 뺄셈인 경우

제거 → 재귀 → 추가

 

3. 곱셈인 경우

곱하기 → 재귀 → 나누기

 

4. 나눗셈인 경우

나누기 → 재귀 → 원 상태로 돌리기 (곱하기)

 

4-1. 나누어지는 수(total)가 0인 경우

연산 후의 total은 0이다.

 

4-2. 나누어지는 수와 나누는 수의 부호가 같은 경우

연산 후의 total은 양수이다.

 

4-3. 나누어지는 수와 나누는 수의 부호가 다른 경우

연산 후의 total은 음수이다.

 

 

● 주의 할 것

: 나눗셈은 몫만 남겨서 연산하므로

다시 원 상태로 돌려놓을 때 곱셈을 하지말고

재귀 전에 임시로 저장해놓은 값을 이용한다.

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// num : 숫자 하나씩 저장
// four : 각 사칙연산의 갯수 저장
int num[12];
int four[4];
int N, sol_max = -1000000000, sol_min = 1000000000;

void program(int cnt, int total)
{
    // 만들 수 있는 식을 다 만들어 본 경우
    if(cnt == N - 1)
    {
        if(total < sol_min)
            sol_min = total;
        if(sol_max < total)
            sol_max = total;
        
        return ;
    }
    
    // 맨 처음인 경우
    if(cnt == 0)
        total = num[cnt];
    
    // 사칙연산 하나씩 확인
    for(int i = 0; i < 4; i++)
    {
        // 사칙연산의 갯수가 없는 경우
        if(four[i] == 0)
            continue;
        
        // 덧셈인 경우
        if(i == 0 && 0 < four[i])
        {
            total += num[cnt + 1];
            four[i]--;
            program(cnt + 1, total);
            four[i]++;
            total -= num[cnt + 1];
        }
        
        // 뺄셈인 경우
        else if(i == 1 && 0 < four[i])
        {
            total -= num[cnt + 1];
            four[i]--;
            program(cnt + 1, total);
            four[i]++;
            total += num[cnt + 1];
        }
        
        // 곱셈인 경우
        else if(i == 2 && 0 < four[i])
        {
            total *= num[cnt + 1];
            four[i]--;
            program(cnt + 1, total);
            four[i]++;
            total /= num[cnt + 1];
        }
        
        // 나눗셈인 경우
        else if(i == 3 && 0 < four[i])
        {
            four[i]--;
            
            // 나누어지는 수가 0인 경우
            if(total == 0)
            {
                int temp = total;
                total = 0;
                
                program(cnt + 1, total);
                total = temp;
            }
            
            // 나누어지는 수와 나누는 수의 부호가 같은 경우
            else if((total < 0 && num[cnt + 1] < 0) || (0 < total && 0 < num[cnt + 1]))
            {
                int temp1 = total;
                if(total < 0)
                    total *= -1;
                
                int temp2 = num[cnt + 1];
                if(num[cnt + 1] < 0)
                    temp2 = -num[cnt + 1];
                
                total /= temp2;
                
                program(cnt + 1, total);
                
                total = temp1;
            }
            
            // 나누어지는 수와 나누는 수의 부호가 다른 경우
            else
            {
                int temp1 = total;
                if(total < 0)
                    total *= -1;
                
                int temp2 = num[cnt + 1];
                if(num[cnt + 1] < 0)
                    temp2 = -num[cnt + 1];
                
                total /= temp2;
                
                total *= -1;
                
                program(cnt + 1, total);
                
                total = temp1;
            }
            
            four[i]++;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 숫자 입력
    for(int n = 0; n < N; n++)
        cin >> num[n];
    
    // 사칙연산의 갯수 입력
    for(int f = 0; f < 4; f++)
        cin >> four[f];
    
    // 재귀 시작
    program(0, 0);
    
    // 정답 출력
    cout << sol_max << "\n" << sol_min;
    
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [531 - 브루트 포스 - 재귀 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	6603	로또	https://pirateturtle.tistory.com/301
2	1182	부분수열의 합	https://pirateturtle.tistory.com/302
3	14225	부분수열의 합	https://pirateturtle.tistory.com/303
4	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/304
5	15658	연산자 끼워넣기 (2)	https://pirateturtle.tistory.com/305
6	14500	테트로미노	https://pirateturtle.tistory.com/306
7	16197	두 동전	https://pirateturtle.tistory.com/307
8	16198	에너지 모으기	https://pirateturtle.tistory.com/308
9	9663	N-Queen	https://pirateturtle.tistory.com/309
10	2580	스도쿠	https://pirateturtle.tistory.com/310
11	4574	스도미노쿠	https://pirateturtle.tistory.com/311
12	1987	알파벳	https://pirateturtle.tistory.com/312