[백준] 15658번 - 연산자 끼워넣기 (2) (C++) 문제 및 풀이

문제) 백준 - 백트래킹 - 연산자 끼워넣기(2)

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

15658번: 연산자 끼워넣기 (2)

 

처음에 permutations를 활용하기 위해 파이썬으로 시도했다가 TLE로 틀려, C++을 통한 백트래킹으로 해결했습니다. 부분합, 인덱스, 4가지 연산자의 개수를 매개변수로 백트래킹을 적용합니다.

 

C++ 소스코드)

	void dfs(int total,int idx, int pp, int mi, int mul, int div) {
	if (idx == N) {
	res_min = min(res_min, total);
	res_max = max(res_max, total);
	return;
	}
	if (pp < oper[0])
	dfs(total + arr[idx], idx + 1, pp + 1, mi, mul, div);
	if (mi < oper[1])
	dfs(total - arr[idx ], idx + 1, pp , mi + 1, mul, div);
	if (mul < oper[2])
	dfs(total * arr[idx], idx + 1, pp , mi, mul + 1, div);
	if (div < oper[3])
	dfs(total / arr[idx], idx + 1, pp, mi, mul, div + 1);
	}

view raw 15658.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/15658_%EC%97%B0%EC%82%B0%EC%9E%90%20%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0(2).cpp 

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions