백준 [14888] - 연산자 끼워넣기

연산자 끼워넣기

전형적인 백트래킹 문제이다. 연산자의 수는 N - 1이지만 연산자의 종류는 4가지 이기때문에, for문을 0 ~ 3까지 돌면서 각각의 연산자가 0보다 큰수, 즉 사용가능한지 먼저 확인하고, 만약 조건을 만족하면 해당 연산자를 가지고 이전 값과 함께 계산을 해 주었다.

연산자를 사용할경우 연산자 수를 -= 1 해서 사용을 했다는 표시를 남겼고, 백트래킹에서 나왔을때는 다시 += 1 을 해주는식으로 해서 여러 경우의 수를 계산하였다.

for(i = 0; i < 4; i++) {
	if (sign[i] != 0) {
		switch (i) {
			case 0:
				A += (array[current]);
				break;
			case 1:
				A -= (array[current]);
				break;
			case 2:
				A *= (array[current]);
				break;
			case 3:
				A /= array[current];
				break;
			}
       }

A는 지금까지의 누적된 값. current는 현재 사용하는 수열의 위치를 나타내고, 만약 current == N, 즉 모든 수열에 대한 계산이 끝났을경우 if문을 타서 min과 max의 값과 비교하고 갱신해주었다. 

위에 올린 사진에는 안나와있지만, 예상되는 출력값은 10억과 -10억을 넘지 않는다고 써져있어서, min과 max값을 10억1과 -10억1을 초반값으로 주고 이를 갱신하는 방식으로 코드를 풀었다.