https://www.acmicpc.net/problem/16637
16637번: 괄호 추가하기
첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가
www.acmicpc.net
문제
정수 0 ~ 9 중 하나의 수와 우선 순위가 동등한 연산자 '+, -, x' 중 하나가 차례로 나와 하나의 수식을 이룰 때, 해당 수식에 임의의 겹치지 않는 괄호를 추가해 최댓값을 구하는 문제이다.
풀이 과정
괄호가 올 수 있는 모든 경우의 수를 완전 탐색했다. 괄호가 쳐진 것은 used_oper 배열에 표시하고, 괄호를 치기 전 해당 연산자 이전, 이후 연산자 중 괄호가 쳐진 것이 있다면 숫자가 겹치므로 다음으로 continue 했다. 괄호의 수가 정해진 것이 아니므로 다른 탈출 조건은 주지 않았고, 모든 경우의 수에서 해당 상태의 수식을 계산하며 최댓값을 갱신했다.
수식을 계산할 때는 nums, opers, used_oper을 이용해 새로운 nums_temp와 opers_temp를 만들고 계산했다. 만약 괄호가 쳐진 곳이 아니라면 계속해서 nums_temp와 opers_temp에 값을 넣어주고, 괄호가 쳐진 곳은 oper함수로 연산을 수행한 값을 nums_temp에 넣고 다음 opers값을 opers_temp에 넣었다. 그리고 인덱스가 전체적으로 한번 건너갔으므로 i를 추가로 증가시켜줬다. nums_temp와 opers_temp가 완성된 후에는 모든 연산자의 우선 순위가 동등하므로 차례로 계산해 값을 구했다.
느낀 점
여러 인덱스들을 설정하는 과정에서 범위가 초과되는 것을 계속해서 디버깅해보며 수정했다. 오랜만에 문제를 풀다보니 범위에 대한 감이 모호해진 것 같다. 그리고 해당 문제의 값이 음수가 될 수도 있는데, ret을 0으로 두고 풀어 오답을 받기도 했다. 최대 최소를 구할 때는 문제 답의 범위를 생각해보고 알맞은 값으로 초기화를 잘해주자. 최대값을 구할 때는 문제의 최소값 이하의 값으로, 최소값을 구할 때는 문제의 최댓값 이상의 값으로 초기화를 해주자.
문제를 푸는데 너무 오랜 시간이 걸렸다. 전체적인 틀은 금세 떠올랐지만 맵이나 그래프가 아닌 새로운 형태의 탐색에 취약했던 것 같다. 나에게는 큰 틀을 여러 곳에 응용하는 훈련이 되어서 좋은 문제였다.
#include<bits/stdc++.h>
using namespace std;
int n, ret = -987654321;
char temp;
vector<int> nums;
vector<char> opers;
bool used_oper[9];
//연산자 함수
int oper(int a, int b, char oper) {
if (oper == '+') return a + b;
else if (oper == '-') return a - b;
return a * b;
}
//used_oper을 기준으로 현재 상태의 값 연산
int calcul() {
//괄호를 기준으로 새로운 nums_temp와 opers_temp (새로운 수식)을 구함
vector<int> nums_temp;
vector<char> opers_temp;
int val = 0;
for (int i = 0; i < n / 2; i++) {
if (!used_oper[i]) {
nums_temp.push_back(nums[i]);
opers_temp.push_back(opers[i]);
}
else {
nums_temp.push_back(oper(nums[i], nums[i + 1], opers[i]));
if (i < n / 2 - 1) opers_temp.push_back(opers[i + 1]);
i++; //한 단계씩 건너뛰었으므로
}
}
//마지막 수 추가
if (nums_temp.size() == opers_temp.size()) nums_temp.push_back(nums[n / 2]);
//구한 수식을 기준으로 연산
val = nums_temp[0];
for (int i = 0; i < opers_temp.size(); i++) {
val = oper(val, nums_temp[i + 1], opers_temp[i]);
}
return val;
}
//괄호가 올 수 있는 모든 경우의 수 탐색
void go(int idx) {
//현 상태값 계산 후 최댓값 갱신
int cur = calcul();
ret = max(ret, cur);
//모든 경우의 수 탐색, 불가능한 경우 continue;
for (int i = idx; i < n / 2; i++) {
if (idx == 0) {
if (used_oper[i + 1]) continue;
}
else if (idx == n / 2 - 1) {
if (used_oper[i - 1]) continue;
}
else {
if (used_oper[i - 1] || used_oper[i + 1]) continue;
}
//방문
used_oper[i] = true;
//다음 인덱스부터 재탐색
go(i + 1);
//원상 복구
used_oper[i] = false;
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//입력
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
if (i % 2 == 0) nums.push_back(atoi(&temp));
else opers.push_back(temp);
}
//함수 실행
go(0);
//출력
cout << ret;
return 0;
}'알고리즘 : C++ > BaekJoon' 카테고리의 다른 글
| 백준 12869번 - 뮤탈리스크 (0) | 2023.06.13 |
|---|---|
| 백준 4179번 - 불! (0) | 2023.06.02 |
| 백준 16234번 - 인구 이동 (2회 차) (0) | 2023.06.02 |
| 백준 2589번 - 보물섬 (2회 차) (0) | 2023.06.02 |
| 백준 15686번 - 치킨 배달 (2회 차) (0) | 2023.06.01 |