[코드트리] 연산자 배치하기 (삼성 SW 역량테스트 2017 하반기 오후 2번)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/arrange-operator

이후 설명 및 입/출력은 링크 참고

 

연산자 배치하기 문제 풀이는 BOJ 14888 : 연산자 끼워넣기와 같다.

#include <stdio.h>

#define MAX (100 + 20)

int T;
int N;
int numbers[MAX];
int possible[5];
int minAnswer, maxAnswer;

void input()
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++) scanf("%d", &numbers[i]);
	for (int i = 0; i < 4; i++) scanf("%d", &possible[i]);
}

int calculator[MAX];
int visit[MAX];

int calculate()
{
	int sum;

	sum = numbers[0];

	for (int i = 0; i < N - 1; i++)
	{
		if (calculator[i] == 0) sum += numbers[i + 1];
		else if (calculator[i] == 1) sum -= numbers[i + 1];
		else if (calculator[i] == 2) sum *= numbers[i + 1];
		else if (calculator[i] == 3) sum /= numbers[i + 1];
	}

	return sum;
}

void DFS(int L)
{
	if (L > N - 2)
	{
		int tmp = calculate();
		if (maxAnswer < tmp) maxAnswer = tmp;
		if (minAnswer > tmp) minAnswer = tmp;
	}

	for (int i = 0; i < 4; i++)
	{
		if (visit[i] == possible[i]) continue;

		calculator[L] = i;

		visit[i]++;
		DFS(L + 1);
		visit[i]--;
	}
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		minAnswer = 0x7fff0000;
		maxAnswer = -0x7fff0000;

		DFS(0);

		printf("%d %d\n", minAnswer, maxAnswer);
	}

	return 0;
}