#100. [백준_C언어] 14888 : 연산자 끼워넣기 \ 백트래킹

 

입력 코드

#include <stdio.h>

int max=-1000000002, min=100000002;
int n;
int p,m,t,d;
int g[12];

void dfs(int a,int b,int p,int m,int t,int d)
{
	if(a==n)
	{
		if(max<b) max=b;
		if(min>b) min=b;
		return;
	}
	else
	{
		if(p>=1)
		dfs(a+1,b+g[a],p-1,m,t,d);
		if(m>=1)
		dfs(a+1,b-g[a],p,m-1,t,d);
		if(t>=1)
		dfs(a+1,b*g[a],p,m,t-1,d);
		if(d>=1)
		dfs(a+1,b/g[a],p,m,t,d-1);
	}
}
int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&g[i]);
	}
	scanf("%d %d %d %d",&p,&m,&t,&d);
	dfs(1,g[0],p,m,t,d);
	printf("%d\n%d",max,min);
}

출처 www.acmicpc.net/source/10501819

 

 

코드 설명

#백트래킹 #브루트포스 알고리즘

 

 

문제 출처

www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net