BOJ 14888 : 연산자 끼워넣기 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/14888

 

숫자가 N개 연산자가 N-1개가 있다.

연산자는 4종류고, 중복으로 사용이 가능한 경우다.

보통 DFS에서 visit(check, used)으로 현재의 값(여기에서는 연산자)을 사용 중인지 확인하고,

DFS를 다음 단계로 보낸다.

void DFS(int L)
{
	if (/* return 조건 */) return;


	for (int i = 0; i < 4; i++)
	{
		if (visit[i] == 1) continue; /* 사용 중이면 패스 */

		visit[i] = 1; /* 다음 dfs에서 선택하지 못하도록 표시 */
		DFS(L + 1);
		visit[i] = 0; /* dfs 종료, 원상태로 복구 */
	}
}

 

visit을 최대 possible까지 허용한다면?

아래와 같이 코드를 수정하면 된다.

void DFS(int L)
{
	if (/* return 조건 */) return;


	for (int i = 0; i < 4; i++)
	{
		if (visit[i] == possible[i]) continue; /* 최대 허용이면 pass */

		visit[i]++; /* check = 1 대신 ++로 관리 */
		DFS(L + 1);
		visit[i]--; /* 원상태 -> 즉 1 감소 */
	}
}

 

DFS에 각 Level마다 calculator에 연산자 (i = 0 ~ 4 => +, -, *, /)를 저장해두고,

마지막 L에서 계산하면 된다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (100 + 20)

int N;
int numbers[MAX];
int possible[5];

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;
}

int MINANS = 1000000001;
int MAXANS = -1000000001;
void DFS(int L)
{
	if (L > N - 2)
	{
		int tmp = calculate();
		if (MAXANS < tmp) MAXANS = tmp;
		if (MINANS > tmp) MINANS = 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)
{	
	input();

	DFS(0);

	printf("%d %d\n", MAXANS, MINANS);

	return 0;
}

 

실제 A형에서는 tc가 여러 개이므로, MINANS, MAXANS를 잘 초기화 하자.