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

 

안녕하세요 (. ❛ ᴗ ❛.) ~

오늘도 백준 삼성 SW 역량 테스트 기출문제를 풀어보았습니당.

매주 꾸준히 문제를 풀고 싶은데 ㅠㅠ 그게 참 쉽지가 않네요.......★

 

백준 14888번

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

문제를 딱 읽어보면 이 문제가 순열 문제임을 알 수 있습니다!

하지만 일반적인 순열은 아니고, 고등학교 때쯤... 배웠던 것으로 추정되는.. 같은 것이 있는 순열 문제인 것 같습니다.

각각의 연산자는 1개 이상씩 존재하기 때문입니다.

 

우선 저는 입력으로 받은 연산자를 쉽게 표현하기 위해 정수형 배열을 사용하였습니다.

문제에서 주어진 순서대로 덧셈(+)은 1, 뺄셈(-)은 2, 곱셈(×)은 3, 나눗셈(÷)은 4로 표현하였습니다.

해당 문제에서는 각 연산자의 개수가 입력으로 들어오기 때문에

연산자의 개수만큼 연산자에 해당하는 숫자를 추가해주었습니다.

ex) 만약 덧셈(1로 표현)의 개수가 2, 뺄셈(2로 표현)의 개수가 1, 나눗셈(4로 표현)의 개수가 1로 입력이 들어왔다면,

이것을 1 1 2 4 와 같이 표현하였습니다.

 

다음으로 같은 것이 있는 순열을 구현하기 위해 먼저 순열 알고리즘을 작성해보았습니다.

 

순열 알고리즘

 

저는 위의 그림과 같이 주어진 배열을 앞에서부터 탐색을 시작하였고,

탐색 범위 내에서 swap 하여 순열을 구할 수 있었습니다.

(탐색 범위에 숫자가 2개만 남을 때까지 tree의 depth를 늘려나가는 방식입니다!)

최종적으로 탐색 범위의 시작과 끝이 같아지는 지점을 종료 지점으로 설정하였습니다.

 

이를 의사 코드로 나타내면 다음과 같습니다.

저는 문제에서 주어진 N의 범위가 2 이상 11 이하였기 때문에 재귀 함수를 사용하였습니다.

 

// start: 탐색의 시작 범위 (초기 값은 연산자 배열의 첫번째 index)
// end: 탐색의 종료 범위 (연산자 배열의 마지막 index)

void permutation(int start) {
	if (start == end)
		then (식 계산 후 min, max 판별하기)
        
	for (start부터 end까지) {
		swap(start, 현재 탐색 중인 값);
		permutation(start + 1);
		swap(start, 현재 탐색 중인 값);
	}

}

 

swap이 permutation 재귀 함수 앞 뒤로 두 번 필요한 이유는,

permutation 함수 종류 이후 tree의 다른 가지로 뻗어나가기 위해서는 기존의 상태로 되돌아가야 하기 때문입니다.

같은 것이 있는 순열의 경우에는 swap 하는 대상이 같은 값일 때 더 이상 tree를 뻗어나가지 않도록 조절해주면 됩니다.

(어차피 같은 값이기 때문에 swap을 하면 불필요한 반복이 발생하게 됨!)

 

이를 바탕으로 아래와 같이 최종적인 코드를 작성하였습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N, min = 1000000000, max = -1000000000;
int array[101], op[100];
int index = 1;

// 연산자 배열 생성하기
void insert(int value, int count) {
	for (int i=0; i<count; i++)
		op[index++] = value;
}

void swap(int a, int b) {
	int temp = op[a];
	op[a] = op[b];
	op[b] = temp;
}

// 주어진 식 연산
void calculate() {
	int sum = array[1];
	for (int i = 1; i < N; i++) {
		switch (op[i]) {
			case 1:
				sum += array[i + 1];
				break;
			case 2:
				sum -= array[i + 1];
				break;
			case 3:
				sum *= array[i + 1];
				break;
			case 4:
				sum /= array[i + 1];
				break;
		}
	}
	if (sum > max)
		max = sum;
	if (sum < min)
		min = sum;
}

// 같은 것이 있는 순열 구하기
void permutation(int start) {
	if (start == N - 1) {
		calculate();
	}
	for (int i = start; i < N; i++) {
		if (i != start && op[i] == op[start])
			continue;
		swap(i, start);
		permutation(start + 1);
		swap(i, start);
	}

}

int main() {

	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d", &array[i]);
	
	int temp;
	for (int i = 1; i <= 4; i++) {
		scanf("%d", &temp);
		if (temp != 0) {
			insert(i, temp);
		}
	}

	permutation(1);

	printf("%d\n%d\n", max, min);

	return 0;

}

 

피연산자와 연산자를 입력받은 후, insert 함수를 통해 연산자 배열을 생성하여 줍니다. (앞에서 설명한 방식으로)

이후 permutation 함수를 통해 같은 것이 있는 순열을 구한 후,

순열 1개를 구할 때마다 calculate 함수를 통해 해당 식을 계산합니다.

이 함수에서 min과 max 값을 계속해서 업데이트 해나갑니다.

모든 순열을 다 구하게 되면, 구하고자 하는 min과 max 값을 얻을 수 있습니다!

(최댓값은 10억, 최솟값은 -10억이라고 하였기 때문에 초기값을 각각 최솟값과 최댓값으로 설정하였습니다.)

 

이 문제는 연산 순서를 별도로 지키지 않아도 되기 때문에

순열을 구하는 알고리즘만 잘 설계한다면 간단하게 풀 수 있는 문제입니다!