[백준/BOJ] 14888번 연산자 끼워넣기 (C/C++)

백준 온라인 저지(BOJ) 14888번 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

* 사용언어 : C언어, C++

 

1. 문제

N개의 숫자와 N-1개의 연산자(+, -, *, /)가 주어졌을 때

숫자 사이에 연산자를 하나 씩 끼워넣어 만들 수 있는 결과의 최대값과 최소값을 출력

단, 연산자 우선 순위는 무시하고 앞에서부터 순서대로 연산함

(결과는 -10억보다 크거나 같고 10억보다 작거나 같음, 중간 결과도)

 

2. 풀이

DFS를 활용하여 간단하게 풀 수 있는 문제입니다.

N개의 숫자를 1차원 배열에 넣고, 배열의 index를 DFS의 depth로 보는 방식입니다.

 

문제에서 연산자의 개수는 search 알고리즘에서 흔히 사용하는 visited 배열처럼 제공됩니다.

이를 일반적인 visited 배열처럼 활용하여 문제를 풀었습니다.

 

예를 들어 일반적인 dfs에서 방문 여부를 확인하는 부분은 연산자가 남아있는지 확인하는 방식으로 구현했고,

다음 depth의 dfs 호출 전/후로 visited 값을 0 → 1 → 0으로 바꾸는 부분은

연산자 개수를 줄였다가 늘리는 방식으로 처리하여 일반적인 dfs와 동일한 구조로 구현할 수 있었습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
14888_연산자 끼워넣기
1112KB	0ms
*/
#include <cstdio>

int N, a[11], op[4];
int max = -1e9;
int min = 1e9;

void dfs(int depth, int res) {
	if (depth == N) {
		if (res > max) max = res;
		if (res < min) min = res;
		return;
	}

	for (int i = 0; i < 4; ++i) {
		if (op[i] == 0) continue;

		--op[i];

		if (i == 0)
			dfs(depth + 1, res + a[depth]);
		else if (i == 1)
			dfs(depth + 1, res - a[depth]);
		else if (i == 2)
			dfs(depth + 1, res * a[depth]);
		else
			dfs(depth + 1, res / a[depth]);

		++op[i];
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", &a[i]);
	for (int i = 0; i < 4; ++i) scanf("%d", &op[i]);

	dfs(1, a[0]);
	printf("%d\n%d\n", max, min);
	return 0;
}

* 1e9는 1,000,000,000(10^9)입니다.