4008. 숫자 만들기

static int N;
static int ops[4]; // +, -, *, /
static int numbers[12];
static int seq[11];
static int maximum, minimum;

static void __solution(int cnt)
{
	if (cnt >= N - 1)
	{
		int ret = numbers[0];
		for (int i = 1; i < N; i++)
		{
			//헷갈릴 수 있으니, seq에 대한 인덱스도 따로 만들어서 사용하기를 권장,
			if (seq[i - 1] == 0) 
				ret += numbers[i];
			else if (seq[i - 1] == 1)
				ret -= numbers[i];
			else if (seq[i - 1] == 2)
				ret *= numbers[i];
			else
				ret /= numbers[i];
		}
		
		if (ret > maximum)
			maximum = ret;
		if (ret < minimum)
			minimum = ret;
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			if (ops[i] > 0)
			{
				ops[i] -= 1;
				seq[cnt] = i;
				__solution(cnt + 1);
				ops[i] += 1;
			}
		}
	}
}

static int solution()
{
	scanf("%d", &N);
	for (int i = 0; i < 4; i++)
		scanf("%d", &ops[i]);
	for (int i = 0; i < N; i++)
		scanf("%d", &numbers[i]);
	maximum = -100000001; //주의, 최대 값 초기 설정 시 가급적 음수 값으로,
	minimum = 100000001; //
	__solution(0);
	return maximum - minimum;
}

최대, 최소는 가급적 모든 경우를 다 따져보는 것이 좋다.

그래서 위 문제의 핵심은 연산자를 어떻게 섞을 것인가 이다. 그리고 이는 같은 것이 있는 순열을 구현 하는 것으로 귀결된다.

 

순열이기 때문에, 매 재귀 시 마다 i = 0 부터 시작한다. 매 재귀 시 마다 해당 연산자를 더 사용 할 수 있다면 이를 연산자 순서 정보를 담는 배열에 저장하여 다음 재귀로 넘기는 것이다.

더 사용 할 수 없는 연산자라면 다음 연산자가 있는지 확인 해보는 것이다.

그리고 재귀의 특색에 맞게 재귀가 끝난 뒤에는 사용한 연산정보를 다시 되돌려놔야 한다.

 

이렇게 해서 연산자 순서를 하나 만들면 해당 연산자 순서를 이용하여 어떤 값이 나오는지 계산해보아야 한다.

1 2 3 4 5 

  + + - *

이렇게 되므로, number 배열을 순회할 때는 인덱스 1부터 시작하게 된다.

그러나 seq 배열은 논리적으로 위와 같을 뿐이므로 실제 사용을 위해서는 i - 1을 사용하거나, 해당 seq배열을 순회하기 위한 또 다른 인덱스 하나를 0으로 초기화 해서 사용해야 한다. 이 부분을 놓쳐서 생각보다 디버깅이 오래 걸렸다.

 

이렇게 하면 대부분의 샘플 테스트 케이스는 맞는다. 그러나 한가지 문제가 더 있었는데, 일부 테스트 케이스에 대해서는 오답을 내고 있었다.

왜냐하면 maximum의 초기 값을 설정 시 문제가 있었기 때문이다. minimum은 큰 상관이 없었는데, 처음에는 maximum의 초기값을 0으로 설정하였다. 기존에 문제를 풀 때 주로 0으로 초기화해서 풀어왔기 때문이다.

그러나 이렇게 초기화 하면 음수에 대해서 최대 값을 구할 수 없다. 당연하게도 음수에 대해서는 0이 항상 더 크기 때문이다.

그래서 unsigned가 붙었는지 여부에 따라 minimum은 기존에 하던대로 0x7fffffff이 되는 것이 맞고, maximum  

 

//주의사항 및 정리

1. 두 배열을 동시에 사용해야 하는 경우 가급적 각각의 인덱스를 따로 선언하여 각 배열에 맞게 사용 할 것.

2. 최대, 최소값 초기화 시, 역설적이게도 최대는 최소가되도록 해야하고, 최소는 최대가 해야한다. 

->minimum은 기존에 하던대로 0x7fffffff로 해도 무방하고, 

->maximum은 부호가 없는 경우에는 0으로 있는 경우에는 -20억 쯤으로 하는 것이 맞다.