https://www.acmicpc.net/problem/14888
문제
> N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다.
> 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다.
> 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
> 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다.
이때, 주어진 수의 순서를 바꾸면 안 된다.
> 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고,
주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다.
예를 들어, 아래와 같은 식을 만들 수 있다.
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
> 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.
> 또, 나눗셈은 정수 나눗셈으로 몫만 취한다.
> 음수를 양수로 나눌 때는 C++14의 기준을 따른다.
> 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.
> 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7
> N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.접근
재귀로 DFS를 구현해 백트래킹으로 풀어낸다.
재귀를 돌며 연산의 가능한 모든 경우가 따져진다.
N이 3일 때를 예로들어보면 처음에 dfs(1, 3)이 들어간다.
op(0), 덧셈계산이 1개 있으므로 op(0)의 개수를 줄이고 dfs(2, 3+4)로 다시 재귀에 들어간다.
여기서 방금 op(0)을 해서 0이 됐으므로 다음 연산인 op(2) 곱셈으로 넘어간다. op(2)가 0이 되고
여기서 dfs(3, 7x5)로 재귀에 들어간다.
이제 재귀의 탈출조건인 i가 N이랑 같을 때에 걸려 최대, 최소값이 갱신되고 dfs(3, 35)가 종료된다.
그럼 아까 dfs(3, 35)를 넘겼던 다음 명령이 호출된다. 그래서 op(2)가 ++로 다시 1이 되고 추가연산이 없으므로 해당 재귀도 끝난다.
그래서 dfs(2, 7)을 만들었던 op(0)++이 있는 곳으로 돌아가 op(0)이 다시 1이 된다. 이 다음에 op(2)로 가서 dfs(3,35)가 다시 넘어가지만 이미 본거라 변화가 없다.
그럼 이제 dfs(2,7)도 완전히 끝나 dfs(1, 3)일때의 op(0)++로 돌아가 op(0)이 다시 1이 되고 op(2)로 넘어간다.
여기서 dfs(2, 3x4)가 재귀로 호출된다. 직전에 op(0)을 1로 만들었기 떄문에 dfs(3, 12+5)가 재귀된다.
i = N이랑 같으므로 최대는 35 그대로, 최소는 17로 갱신 되며 재귀가 깨진다.
다시 op(0)++로 돌아와 1로 만들어주고 쭉 내려가는데 이땐 op(2)에 대해 진행중이었던거라 0이라 추가 연산없이 재귀가 깨진다.
그래서 dfs(2, 12)가 깨지고 op(2)가 1로 되고
추가연산이 없으므로 dfs(1, 3)에 대한 재귀도 깨져 결과가 나오게 된다.
문제해결
> 연산은 4가지라 크기 4로 선언하고, 어떤 계산에도 최소 -10억, 최대 10억이 나온다고 했으므로 이를 최대 최소 갱신을위한 기준 값으로 잡아준다. 재귀 dfs로 백트래킹을 구현한다.
> 탈출조건으로 모든수의 연산이 끝났을때(i == N)으로 주고 최대, 최소값을 갱신해준다.
> 첫 덧셈연산에 대해 구현한다. 덧셈연산을 한개 사용하므로 --해주고 다음 연산을 위해 재귀로 수열의 다음수를 사용하기 위해 i+1로 인덱스를 넘기고, 연산결과를 넘긴다.
재귀가 깨지면 다른 경우를 위해 다시 연산갯수를 ++로 복구시킨다.
뺄셈, 곱셈은 같은 맥락이다.
> 나눗셈에선 문제에 조건을 주었기 때문에 이를 고려해준다.
현재 까지의 결과가 음수면 부호를 떼고 몫을 구해낸 뒤 부호를 붙여준다. 양수면 그대로 몫만 구해준다.
> main 함수에서 수열, 연산별 갯수를 입력받아주고 dfs로 시작인덱스 첫 값을 넘긴다. 여기서 num[0]을 넘겨야 예를 들어 첫 덧셈에 걸렸을 때, num[0]+num[1]이런식으로 제대로된 결과를 얻을 수 있다.
> 최대, 최소값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int N;
vector<int> num;
vector<int> op(4); // +, -, *, /
int Max = -1000000000;
int Min = 1000000000;
void dfs(int i, int sum)
{
if (i == N)
{
Max = max(Max, (int)sum);
Min = min(Min, (int)sum);
return;
}
if (op[0] > 0)
{
op[0]--;
dfs(i + 1, sum + num[i]);
op[0]++;
}
if (op[1] > 0)
{
op[1]--;
dfs(i + 1, sum - num[i]);
op[1]++;
}
if (op[2] > 0)
{
op[2]--;
dfs(i + 1, sum * num[i]);
op[2]++;
}
if (op[3] > 0)
{
op[3]--;
if (sum < 0) dfs(i + 1, -1 * (abs(sum) / num[i]));
else dfs(i + 1, sum / num[i]);
op[3]++;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
num.resize(N);
for (int i = 0; i < N; i++) cin >> num[i];
for (int i = 0; i < 4; i++) cin >> op[i];
dfs(1, num[0]);
cout << Max << '\n' << Min << '\n';
}
후기
최대가 나오는경우, 최소가 나오는 경우별로 어떤 연산자 순서로 와야 그렇게 나오는지를 생각해 단순 구현으로 했을 때 예제 3에대한 결과는 나왔다. 근데 짜맞추기 식이여서 다른 예제는 안됐다.
도저히 갈피가 잡히지 않아 참고 자료를 보면서 이해했다.
처음에 딱 봤을 때, 이게 모든 경우를 다 돈다고? 라고 생각했지만 3을 예시로 전부 써가며 따라가 보니 신기하게 전부 고려가 됐다. 문제에 이해는 했지만 다른 문제를 풀어보긴 아직 벅찰것 같다. 백트래킹 문제를 집중공략해보자.
