[백준알고리즘] 14888번 : 연산자 끼워넣기 #스터디 3주차

문제는 아래 사이트에 들어가면 확인 할 수 있다. 

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

14888번: 연산자 끼워넣기

 

 

 

먼저 변수 선언이다. 

N : 수열 내의 수의 개수

operand : 수열을 다룰 배열

operator_ : 연산자 배열, 각 연산자별로 개수가 입력됨

ret_,min, ret_max : return 될 min값과 max값, 식의 결과는  항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

여기서 min의 초기값이랑 max의 초기값이 왜 가장 큰 값과 가장 작은값일 까 그 이유는 dfs함수 내에서 설명하겠다. 

 

 

< main 함수 >

먼저 변수 N에 수열내부에 들어갈 수의 개수를 입력한다. 

그 후 N번만큼의 for문을 돌려서 수열배열(operand)에 입력하였다.

operator 역시 4번 반복하여 + - * /의 개수를 입력했다. 

 

마지막으로 dfs를 돌려서 계산을 한다.

인자값으로 operand[0]과 0을 주었다.

max값과 min값을 출력해주면 메인 완성이다.

 

 

< dfs 함수 >

 

dfs 함수 내부 1) : ret_min과 ret_max 값 설정하기

 

 operand[0]과 0이 각각 result와 cnt로 복사되었는데 이는 현재 계산할 값과 현재 계산을 얼만큼 했는지를 나타낸다. 

cnt가 N-1의 값이 되었을 때, dfs로 재귀하며 계산하다가, cnt가 N-1까지 온 것이기 때문에 결과만 나타내주면 되는 상황이다.

 

cnt == N-1일 때 result의 값의 크기를 각각 ret_max와 ret_min과 비교하여 값을 할당한다. 

 min의 초기값 가장 큰 값(10억) 이기 떄문에 result가 작은 값이 나올때마다 ret_min이 업데이트 된다. 또 이 변수가 전역변수이기 때문에 가장 작은 값을 할당 받을 수 있는 것이다. 

max는 위의 설명과 반대의 경우이다.

return 을 통해 타고 들어왔던 dfs를 순차적으로 탈출할 수 있게 하였다. 

 

 

dfs 함수 내부 2) : operator에 따른 계산 결과 확인

 

operator는 총 4종류가 있고 operand 사이 어디든지 들어갈 수 있다. 그리고 우선순위를 생각하지 않아야 한다. 즉 계산을 한개씩 차례대로 해주어야 한다는 것이다. 

for 문을 돌려서 operator 4종류를 모두 확인해주었다. 

operator_[i] 안에 들어간 값은 각 연산자들의 개수이므로 0개이면 사용하면 안된다. 

그래서 0이 아닐 때라는 조건을 만들었다. 

조건 안에서 -- operator_[i]를 함으로써 그 연산자 1개를 사용했다는 것을 표시해었다. 

 

그 후 모든 조건을 확인하기 위하여 index 값에 따라 결과를 생성해서 매개변수 result에 인자값으로 전달해주었다. cnt역시 1 증가해서 전달했다. 

 

마지막에 ++operator_[i]는 operator_ 사용한 것을 취소함을 의미한다고 한다(여기는 헷갈려서 좀 찾아봤는데 아직 이유를 잘 모르겠다 ㅠㅠ 나중에 알고나면 수정하겠다. )

 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <algorithm> #include <cstring> #include <iostream> #include <vector> #include<stdio.h> using namespace  std;   int N; // 수의 개수 2부터 11 int operand[11];//수열 An int operator_[4]; //연산자 + - * / 의 개수 int ret_min = 100000000, ret_max = -100000000;   //중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.   vector <int> v; void dfs(int result, int cnt) { //현재까지 계산된 결과     if (cnt == N - 1) {         if (ret_min > result) {             ret_min = result;         }         if (ret_max < result) {             ret_max = result;         }         return;     }       for (int i = 0; i < 4; ++i) {         if (operator_[i] != 0) {             --operator_[i];               if (i == 0) {//  +                 dfs(result + operand[cnt + 1], cnt + 1);             }else if (i == 1) {    //  -                 dfs(result - operand[cnt + 1], cnt + 1);             }else if (i == 2) {//  *                 dfs(result * operand[cnt + 1], cnt + 1);             }else if (i == 3) {//  /                 dfs(result / operand[cnt + 1], cnt + 1);              }                  ++operator_[i];         }     } } int main() {       cin >> N; //수열안의 수의 개수 입력          for (int i = 0; i < N; ++i) {         cin >> operand[i]; //수열 입력     }     for (int i = 0; i < 4; ++i) {         cin >> operator_[i]; // + - * / 각각의 개수 입력      }           dfs(operand[0], 0);  //현재 값(첫번째 값), (현재 operand의 취치)어디까지 계산했는지          cout << ret_max <<"\n"<< ret_min ;       return 0; } Colored by Color Scripter

cs