BOJ 16637 : 괄호 추가하기 (A형 상시)

 

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

 

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

 

www.acmicpc.net/problem/16637

 

 

첫 번째 예시를 보자.

연산자는 + * - * 로 총 4개이다. 순서대로 1, 2, 3, 4번째 연산자로 정의하자.

 

먼저 괄호 안에는 연산자가 하나만 들어있어야 하므로, 1번 연산자에 괄호를 만들면, 2번 연산자는 괄호가 불가능하다.

→ (3 + 8) * 7 - 9 * 2

 

따라서 DFS로 아래의 경우의 수가 되도록 만든다.

 

0 0 0 0 → 괄호가 없는 경우
0 0 0 1 → 4번 연산자에만 괄호를 만든 경우
0 0 1 0
0 1 0 0
0 1 0 1 → 2번, 4번 연산자에 괄호를 만든 경우
1 0 0 0
1 0 0 1
1 0 1 0 

 

1 2 3 4 연산자 중, 괄호를 만드는 경우를 1로 아닌 경우를 0으로 표시한다.

 

L번째 연산자에 괄호를 선택하지 않으면 L + 1번째로 넘긴다.

L - 1번째 연산자를 선택하지 않은 경우에 L번째 연산자를 선택할 수 있고, 선택하게 된다면 L + 2번째로 넘긴다.

(L + 1번째는 선택할 수 없기 때문이다.)

 

연산자는 항상 N / 2개 있으므로 halfN만큼만 DFS를 진행한다.

int list[10 + 2];

void outputList()
{
	for (int i = 1; i <= halfN;i++) printf("%d ", list[i]);
	putchar('\n');
}

void DFS(int L)
{
	if (L > halfN) /* halfN = N의 절반 */
	{
		outputList();
        
        ...
        
		return;
	}

	list[L] = 0; /* 괄호 선택하지 않기 */
	DFS(L + 1);

	if (list[L - 1] == 0) /* 앞의 연산자에 괄호가 없다면 */
	{
		list[L] = 1; /* 괄호를 선택 */
		DFS(L + 2);
		list[L] = 0; /* 초기화 */
	}
}

outputList로 debugging 해보면 위와 같은 경우의 수가 만들어진 것을 알 수 있다.

 

경우의 수를 만들었으므로 계산을 해야 한다. 계산한 값을 비교하여 최댓값이 나올 때까지 갱신한다.

int MAXANS = 0x80000000;
void DFS(int L)
{
	if (L > halfN)
	{
		//outputList();
		int tmp = findMaxValue();

		if (MAXANS < tmp) MAXANS = tmp;
		return;
	}
    
    ...
    
}

---

findMaxValue는 아래와 같이 구현한다.

 

1) 먼저 copy에 입력받은 수식을 int형으로 복사한다.

2) 그리고 copy의 문자를 숫자로 변경한다. (문자열 '0' ~ '9'인 것만 숫자 0 ~ 9로 변경)

3) list를 보고 0이 있는 경우는 preBoard에 그대로 옮긴다.

4) list를 보고 1이 있는 경우는 먼저 계산한다. list의 N번째 연산자는 copy에서 2 * N - 1 번째의 배열이 된다.

   그리고 계산된 결과를 copy에 적어둔다.

5) preBoard를 보고 계산한다.

 

3) ~ 5)는 그림으로 더 자세히 보자. list가 0 1 0 1 (list[1] ~ list[4])로 가정한다.

 

첫 번째 연산자(list[1] = 0)는 괄호가 없으므로, copy 2칸을 pre로 그대로 옮긴다.

두 번째 연산자(list[2] = 1)는 괄호가 있으므로, copy의 2 * 2 - 1번째 연산자를 미리 계산, copy[2 * 2]에 답을 적는다.

이 때, preBoard에 옮기지는 않는다. 정답인 56을 연산자 오른쪽에 적어두면, 다음 list를 보고 copy가 되기 때문이다.

 

세 번째 연산자(list[3] = 0)는 괄호가 없으므로, copy 2칸을 pre로 그대로 옮긴다.

 

네 번째 연산자(list[4] = 1)는 괄호가 있으므로, 두 번째 연산자에서 계산한 대로 처리한다.

 

모든 list를 보고나면 마지막 한 칸이 남기 때문에 copy를 preBoard에 한 번 더 복사한다.

 

위의 내용을 구현하면 아래와 같다.

int findMaxValue()
{
	int copy[20 + 5] = { 0 };
	int preBoard[20 + 5] = { 0 };

	int len;
	for (len = 0; str[len]; len++) copy[len] = str[len];
	copy[len] = 0;

	for (int i = 0; i < N; i++)
		if ('0' <= copy[i] && copy[i] <= '9') copy[i] -= '0';

	int pcnt, ccnt;
	pcnt = ccnt = 0;
	for (int i = 1; i <= halfN; i++)
	{
		if (list[i] == 0) /* 괄호가 없는 경우 */
		{
			preBoard[pcnt++] = copy[ccnt++];
			preBoard[pcnt++] = copy[ccnt++];

			continue;
		}

		/* 괄호가 있다면 */
		int opNum, tmp;
		
		opNum = i * 2 - 1; /* list의 i번 연산자는 copy에서 2 * i - 1번에 있다. */
		tmp = calculate(copy[opNum - 1], copy[opNum], copy[opNum + 1]);
		copy[opNum + 1] = tmp; /* 연산자 옆에 복사 */
		ccnt += 2; /* copy의 index만 증가 */
	}

	preBoard[pcnt++] = copy[ccnt++]; /* 마지막 한 칸 복사 */

	for (int i = 1; i < pcnt; i += 2)
	{
		int tmp = calculate(preBoard[i - 1], preBoard[i], preBoard[i + 1]);
		
		preBoard[i + 1] = tmp;
	}

	return preBoard[pcnt - 1];
}

 

calculate는 switch문으로 구현하면 된다.

int calculate(int a, int op, int b)
{
	switch (op)
	{
	case '*':
		return a * b;
		break;
		
	case '+':
		return a + b;
		break;

	case '-':
		return a - b;
		break;
	default:	
		break;
	}

	printf("impossible case!\n");
	return -1;
}

 

전체 코드는 아래와 같다.

#include <stdio.h>

int N;
int halfN;
char str[20 + 5];
int list[10 + 2];

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

	halfN = N / 2;
}

void outputList()
{
	for (int i = 1; i <= halfN;i++) printf("%d ", list[i]);
	putchar('\n');
}

int calculate(int a, int op, int b)
{
	switch (op)
	{
	case '*':
		return a * b;
		break;
		
	case '+':
		return a + b;
		break;

	case '-':
		return a - b;
		break;
	default:	
		break;
	}

	printf("impossible case!\n");
	return -1;
}

int findMaxValue()
{
	int copy[20 + 5] = { 0 };
	int preBoard[20 + 5] = { 0 };

	int len;
	for (len = 0; str[len]; len++) copy[len] = str[len];
	copy[len] = 0;

	for (int i = 0; i < N; i++)
		if ('0' <= copy[i] && copy[i] <= '9') copy[i] -= '0';

	int pcnt, ccnt;
	pcnt = ccnt = 0;
	for (int i = 1; i <= halfN; i++)
	{
		if (list[i] == 0)
		{
			preBoard[pcnt++] = copy[ccnt++];
			preBoard[pcnt++] = copy[ccnt++];

			continue;
		}

		int opNum, tmp;
		
		opNum = i * 2 - 1;
		tmp = calculate(copy[opNum - 1], copy[opNum], copy[opNum + 1]);
		copy[opNum + 1] = tmp;
		ccnt += 2;
	}

	preBoard[pcnt++] = copy[ccnt++];

	for (int i = 1; i < pcnt; i += 2)
	{
		int tmp = calculate(preBoard[i - 1], preBoard[i], preBoard[i + 1]);
		
		preBoard[i + 1] = tmp;
	}

	return preBoard[pcnt - 1];
}

int MAXANS = 0x80000000;
void DFS(int L)
{
	if (L > halfN)
	{
		outputList();
		int tmp = findMaxValue();

		if (MAXANS < tmp) MAXANS = tmp;
		return;
	}

	list[L] = 0;
	DFS(L + 1);

	if (list[L - 1] == 0)
	{
		list[L] = 1;
		DFS(L + 2);
		list[L] = 0;
	}
}

int main(void)
{
	input();

	DFS(1);
		
	printf("%d\n", MAXANS);

	return 0;
}

 

실제 A형에서는 tc가 여러 개이므로 MAXANX를 매 tc마다 가장 작은 값으로 초기화하는 코드를 추가한다.