반응형

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

 

16637번: 괄호 추가하기

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순

www.acmicpc.net

 

 

[ 문제풀이 ]

 

dfs를 이용하여 괄호의 위치를 정하고, 그 괄호를 바탕으로 수식을 계산하여 최댓값을 ans에 저장하는 방식으로 풀었습니다.

 

[ 소스코드 ]

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
 
using namespace std;
 
int N;
char arr[20];    //식
int visited[20];    //괄호 여부
int ans = -987654321;
 
void dfs(int level, int limit, int num)
{
    if (level == limit) {
        int ret = arr[0] - '0';
        int before;
        for (int i = 1; i < N; i += 2) {
            if (visited[i] == -1) {    //괄호 안에 있는 연산자라면
                int temp;
                if (arr[i] == '+') {
                    temp = (arr[i - 1] - '0') + (arr[i + 1] - '0');
                }
                else if (arr[i] == '-') {
                    temp = (arr[i - 1] - '0') - (arr[i + 1] - '0');
                }
                else if (arr[i] == '*') {
                    temp = (arr[i - 1] - '0') * (arr[i + 1] - '0');
                }
 
                if (i != 1) {
                    if (arr[i-2] == '+') {
                        ret = ret - (arr[i-1]-'0') + temp;
                    }
                    else if (arr[i-2] == '-') {
                        ret = ret + (arr[i-1]-'0') - temp;
                    }
                    else if (arr[i-2] == '*') {
                        if (arr[i - 1] - '0' == 0) {
                            ret = before * temp;
                        }
                        else {
                            ret = ret / (arr[i - 1] - '0') * temp;
                        }
                    }
                }
                else {
                    ret = temp;
                }
            }
            else {    //괄호 밖의 연산자라면
                if (arr[i] == '+') {
                    ret += arr[i + 1] - '0';
                }
                else if (arr[i] == '-') {
                    ret -= arr[i + 1] - '0';
                }
                else if (arr[i] == '*') {
                    if (arr[i + 1] - '0' == 0) {
                        before = ret;
                        ret = 0;
                    }
                    else {
                        ret *= arr[i + 1] - '0';
                    }
                }
            }
        }
        ans = max(ans, ret);
        return;
    }
 
    for (int i = num; i < N; i++) {
        if (i % 2 == 1) {
            if (visited[i] == 0) {
                visited[i] = -1;
                visited[i + 2] = 1;
                dfs(level + 1, limit, i + 4);
                visited[i] = 0;
                visited[i + 2] = 0;
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    scanf("%s", arr);
 
    for (int i = 0; i <= (N + 1) / 4; i++) {    //괄호의 개수
        dfs(0, i, 1);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 16234번 - 인구 이동 (C++)  (0) 2022.09.02
[ 백준 ] 17135번 - 캐슬 디펜스 (C++)  (0) 2022.09.01
[ 백준 ] 2178번 - 미로 탐색 (C++)  (0) 2022.08.30
[ 백준 ] 11400번 - 단절선 (C++)  (0) 2022.08.29
[ 백준 ] 11266번 - 단절점 (C++)  (0) 2022.08.27

+ Recent posts

티스토리툴바