풀이 보관함
[C++] 백준 14888번: 연산자 끼워넣기 본문
🔗 문제
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,
www.acmicpc.net
🖍 풀이
+) 1e9를 이용해 최대, 최소를 표현하는 방법을 배웠다.
완전 탐색으로 싹싹 뒤져보면 된다.
인자로 입력받은 연산자의 개수를 집어넣고 함수가 한번 호출될 때마다 각 연산자로 연산해준다.
solve(1, A[0], add, sub, mult, div);
💾 소스
#include <iostream>
long long max=-1e9 , min = 1e9;
int N = 0, A[12];
void solve(int idx, int result, int add, int sub, int mult, int div)
{
if(idx == N)
{
max = (max > result ? max : result);
min = (min < result ? min : result);
return;
}
if(add!=0)
solve(idx+1, result+A[idx], add-1, sub, mult, div);
if(sub!=0)
solve(idx+1, result-A[idx], add, sub-1, mult, div);
if(mult!=0)
solve(idx+1, result*A[idx], add, sub, mult-1, div);
if(div!=0)
solve(idx+1, result/A[idx], add, sub, mult, div-1);
}
int main()
{
int add, sub, mult, div;
std::cin >> N;
for(int i=0; i<N; ++i)
std::cin >> A[i];
std::cin >> add >> sub >> mult >> div;
solve(1, A[0], add, sub, mult, div);
std::cout << max << '\n' << min;
return 0;
}