14888 연산자 끼워넣기 (C++)

알고리즘 왕초보인 나에게 꽤 어렵게 느껴져서 기록해본다.

아마 새롭게 접한 유형이라 그런게 아닐까 싶다.

 

전체 코드

#include <iostream>
using namespace std;

int N;
int num[11];
int opr[4];
int m = 1000000001;
int M = -1000000001;

void myans(int result, int cnt){
    if (cnt == N){
        if (result < m){
            m = result;
        }
        if (result > M){
            M = result;
        }
    }
    for (int i = 0; i < 4; i++){
        if (opr[i] > 0){
            opr[i]--;
            if (i == 0){
                myans(result + num[cnt], cnt + 1);
            }
            else if (i == 1){
                myans(result - num[cnt], cnt + 1);
            }
            else if (i == 2){
                myans(result * num[cnt], cnt + 1);
            }
            else if (i == 3){
                myans(result / num[cnt], cnt + 1);
            }
            opr[i]++;
        }
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> num[i];
    }
    for (int i = 0; i < 4; i++){
        cin >> opr[i];
    }
    myans(num[0], 1);
    cout << m << " " << M;
}

 

코드 설명

#include <iostream>
using namespace std;

int N;
int num[11];
int opr[4];
int m = 1000000001;
int M = -1000000001;

첫 줄에 입력 받을 수의 개수를 기록하기 위해 N을 생성했다.

문제에서 N은 2 이상 11 이하라고 했기에 입력 받은 배열의 공간은 최대인 11로 하였다.

연산자의 종류는 +, -, *, / 로 4가지이기에 opr 배열의 크기는 4로 하였다.

문제에서 최대, 최소값을 10억으로 지정했기 때문에 위와 같이 설정했다.

 

void myans(int result, int cnt){
    if (cnt == N){
        if (result < m){
            m = result;
        }
        if (result > M){
            M = result;
        }
    }
    ...
}

이번 문제에 핵심이 되는 myans 함수 부분이다.

이 문제는 결국 모든 경우의 수를 생각해봐야 하는 문제였기에 재귀함수를 사용해야 했다.

 

먼저 myans 함수에는 result와 cnt가 인자로 들어간다.

여기서 result는 결과 값이고 cnt는 배열 num에 입력된 숫자들 중에

몇 번째 숫자를 불러올지에 대한 인덱스 값이다.

 

cnt가 입력한 수의 개수인 N을 만족할 때, 

result와 기존에 있던 최대, 최소값과 비교하여 필요하다면 갱신한다.

 

void myans(int result, int cnt){
    ...
    for (int i = 0; i < 4; i++){
        if (opr[i] > 0){
            opr[i]--;
            if (i == 0){
                myans(result + num[cnt], cnt + 1);
            }
            else if (i == 1){
                myans(result - num[cnt], cnt + 1);
            }
            else if (i == 2){
                myans(result * num[cnt], cnt + 1);
            }
            else if (i == 3){
                myans(result / num[cnt], cnt + 1);
            }
            opr[i]++;
        }
    }
}

 

for loop을 통해 각 연산자들 작업을 수행한다.

연산자를 사용할 필요가 있다면 opr 배열 내 값이 0보다 클 것이므로 조건문을 사용했다.

 

opr배열 내 0번 째 수의 의미는 덧셈 작업을 몇 번 할 것인가를 의미한다.

따라서 재귀함수로 result에 현재 cnt에 해당하는 num값을 더하고,

다음 인덱스 값인 cnt에 해당하는 num을 계산하라는 의미로 cnt에 1을 더해준다.

 

* 난 아직도 opr[i]++;를 왜 하는지 모르겠다.. 추후에 이해하게 되면 글을 추가하겠다.

 

+ 고찰

이제 생각해보니 cnt가 N이 되면 위 작업을 수행하지 않았어도 되었다.

다시 고친다면 if (cnt == N) 이하 조건문들 뒤에 return; 을 선언할 것이다.

 

int main() {
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> num[i];
    }
    for (int i = 0; i < 4; i++){
        cin >> opr[i];
    }
    myans(num[0], 1);
    cout << m << " " << M;
}

마지막으로 main 함수이다.

여기서는 myans(num[0], 1); 부분만 유의하면 될 것 같다.

초기값을 처음에는 0으로 둬야 하는게 아닌가 헷갈렸다.

 

0으로 두면 myans 연산을 한 번 더 돌리게 해야 할 뿐 아니라

초기값 0이 들어왔을 때  주어진 연산자 외에 0 + num[0] 작업을

추가로 돌릴 수 있도록 처리를 해줘야 한다.

 

따라서 내가 작성한 코드를 사용하기 위해서는

myans 함수의 첫 번째 인자로 num[0]을, cnt에는 1을 넣었다.