JUST WRITE IT. HomeArchivesTagsCategories
백준 16637번 괄호 추가하기
|AlgorithmBOJ|

#16637. 괄호 추가하기

Problem

Solution

  1. 어느 연산자에 괄호를 넣을지 정해야 한다.
    괄호는 연산자 연속으로 넣을 수 없다. (1+(3)-2) → 말도 안되는 식
    그렇기에 이전 괄호의 위치를 알고 있어야 한다.
    괄호는 첫 번째에 넣을 필요는 없으며(op[i]≠1)
    이전 괄호의 위치와 2 차이가 나면 안된다.
  2. 괄호를 모두 지정했으면 각 경우에 맞게 식을 계산한다.
  • 괄호가 등장하면 한 번에 계산하고 반환한다.
  • Stack을 사용하여 연산자만 넣는다.
  • Stack이 비어있지 않으면 꺼내어 연산자에 맞게 계산한다.

1 Try

  • *(곱셈)은 괄호가 필요 없을 것이라 생각하여 괄호를 넣어주지 않았다.
    하지만 연산은 왼쪽에서부터 순서대로 진행되기에 곱셈도 괄호가 필요하다.

    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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    #include <iostream>
    #include <stack>
    using namespace std;
    char expr[20];
    bool selected[20];
    int op[10];
    int N, ans, total_bracket;
    int TaskBracket(int start) {
    	int a = expr[start] - '0';
    	int b = expr[start+2] - '0';
    	char opr = expr[start + 1];
    	if (opr == '+') {
    		return a + b;
    	}
    	else {
    		return a - b;
    	}
    }
    void Calculate() {
    	int res = expr[0]-'0', tmp = 0, idx = 0;
    	bool flag = false;
    	stack<char> st;
    	for (int i = 1; i < N; ++i) {
    		if (i != N-1 && selected[i+1]) {
    			tmp = TaskBracket(i);
    			i+=2; 
    			flag = true;
    		}
    		if (!st.empty()) {
    			if (st.top() == '+') {
    				if(flag) res += tmp; 
    				else res += int(expr[i] - '0');
    			}
    			else if (st.top() == '-') {
    				if(flag) res -= tmp;
    				else res -= int(expr[i] - '0');
    			}
    			else {
    				if(flag) res *= tmp; 
    				else res *= int(expr[i] - '0');
    			}
    			st.pop();
    			flag = false;
    		}
    		if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*') {
    			st.push(expr[i]);
    		}
    	}
    	if (res > ans) ans = res;
    }
    void SelectBracket(int n, int cnt, int prior) {
    	if (cnt <= total_bracket) {
    		Calculate();
    	}
    	for (int i = n; i < total_bracket; ++i) {
    		if (selected[op[i]] || op[i] == 1) continue;
    		if (op[i] - prior == 2) continue;
    		selected[op[i]] = true;
    		SelectBracket(i+1, cnt+1, op[i]);
    		selected[op[i]] = false;
    	}
    }
    int main() {
    	cin >> N;
    	for (int i = 0; i < N; ++i) {
    		cin >> expr[i];
    		if (expr[i] == '+' || expr[i] == '-') {
    			op[total_bracket++] = i;
    		}
    	}
    	SelectBracket(0, 0, 0);
    	cout << ans << "\n";
    	return 0;
    }

    2 Try

  • ans(정답)의 초기값을 0으로 설정해서 틀렸다. 정답은 (-2^31, 2^31)의 범위에 속한다.

    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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    #include <iostream>
    #include <stack>
    using namespace std;
    char expr[20];
    bool selected[20];
    int op[10];
    int N, total_bracket, ans;
    int TaskBracket(int start) {
    	int a = expr[start] - '0';
    	int b = expr[start+2] - '0';
    	char opr = expr[start + 1];
    	if (opr == '+') {
    		return a + b;
    	}
    	else if(opr == '-') {
    		return a - b;
    	}
    	else return a * b;
    }
    void Calculate() {
    	int res = expr[0]-'0', tmp = 0, idx = 0;
    	bool flag = false;
    	stack<char> st;
    	for (int i = 1; i < N; ++i) {
    		if (i != N-1 && selected[i+1]) {
    			tmp = TaskBracket(i);
    			i+=2; 
    			flag = true;
    		}
    		if (!st.empty()) {
    			if (st.top() == '+') {
    				if(flag) res += tmp; 
    				else res += int(expr[i] - '0');
    			}
    			else if (st.top() == '-') {
    				if(flag) res -= tmp;
    				else res -= int(expr[i] - '0');
    			}
    			else {
    				if(flag) res *= tmp; 
    				else res *= int(expr[i] - '0');
    			}
    			st.pop();
    			flag = false;
    		}
    		if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*') {
    			st.push(expr[i]);
    		}
    	}
    	if (res > ans) ans = res;
    }
    void SelectBracket(int n, int cnt, int prior) {
    	if (cnt <= total_bracket) {
    		Calculate();
    	}
    	for (int i = n; i < total_bracket; ++i) {
    		if (selected[op[i]] || op[i] == 1) continue;
    		if (op[i] - prior == 2) continue;
    		selected[op[i]] = true;
    		SelectBracket(i+1, cnt+1, op[i]);
    		selected[op[i]] = false;
    	}
    }
    int main() {
    	cin >> N;
    	for (int i = 0; i < N; ++i) {
    		cin >> expr[i];
    		if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*') {
    			op[total_bracket++] = i;
    		}
    	}
    	SelectBracket(0, 0, 0);
    	cout << ans << "\n";
    	return 0;
    }

    3 Try

    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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    #include <iostream>
    #include <limits>
    #include <stack>
    using namespace std;
    char expr[20];
    bool selected[20];
    int op[10];
    int N, total_bracket, ans = numeric_limits<int>::min();
    int TaskBracket(int start) {
    	int a = expr[start] - '0';
    	int b = expr[start+2] - '0';
    	char opr = expr[start + 1];
    	if (opr == '+') {
    		return a + b;
    	}
    	else if(opr == '-') {
    		return a - b;
    	}
    	else return a * b;
    }
    void Calculate() {
    	int res = expr[0]-'0', tmp = 0, idx = 0;
    	bool flag = false;
    	stack<char> st;
    	for (int i = 1; i < N; ++i) {
    		if (i != N-1 && selected[i+1]) { // 괄호인 경우
    			tmp = TaskBracket(i); // 한 번에 계산
    			i+=2; 
    			flag = true;
    		}
    		if (!st.empty()) { // 스택에 연산자가 있을 경우
    			if (st.top() == '+') {
    				if(flag) res += tmp; 
    				else res += int(expr[i] - '0');
    			}
    			else if (st.top() == '-') {
    				if(flag) res -= tmp;
    				else res -= int(expr[i] - '0');
    			}
    			else {
    				if(flag) res *= tmp; 
    				else res *= int(expr[i] - '0');
    			}
    			st.pop();
    			flag = false;
    		}
    		if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*') {
    			st.push(expr[i]);
    		}
    	}
    	if (res > ans) ans = res;
    }
    void SelectBracket(int n, int cnt, int prior) {
    	if (cnt <= total_bracket) {
    		Calculate();
    	}
    	for (int i = n; i < total_bracket; ++i) {
    		if (selected[op[i]] || op[i] == 1) continue; // 첫 번째 연산자에 괄호는 필요 없다.
    		if (op[i] - prior == 2) continue; // 연속적인 괄호는 불가능
    		selected[op[i]] = true;
    		SelectBracket(i+1, cnt+1, op[i]);
    		selected[op[i]] = false;
    	}
    }
    int main() {
    	cin >> N;
    	for (int i = 0; i < N; ++i) {
    		cin >> expr[i];
    		if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*') {
    			op[total_bracket++] = i;
    		}
    	}
    	SelectBracket(0, 0, 0);
    	cout << ans << "\n";
    	return 0;
    }
Algorithm