백트랙킹 - 14888번

3월 1일(수) - 백트랙킹(14888번)

14888번: 연산자 끼워넣기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- + - * / 4가지 각각의 경우에 해당하는 연산 main에서 진행하기에는 너무 복잡할 것으로 예상됨

  그러므로 계산을 진행할 함수를 따로 빼서 진행

- 함수에서 N-1개의 연산자가 모두 입력된 이후에 max 와 min을 정하는 부분은 if에서 진행

- N-1개의 연산자가 모두 입력되기 전에는 else 안에서 진행 -> 이 안에서 다시 + - * / 의 경우에 따른 재귀 진행

  해당 재귀 안에서는 입력된 연산자의 개수를 -1 해주어야하고, 연산자에 따른 계산도 각각 진행해주어야함

- 따라서 계산을 진행하는 함수에 입력되어야하는 입력값은 (+ - * / 의 4가지의 개수)

  그리고 입력된 연산자의 개수를 카운팅 할 (int x), 연산자에 의한 계산값을 저장할 (int sum) -> 총 6개의 입력

- 함수에서의 활용을 위해서 N, max, min 변수들과 num 배열은 모두 전역변수로 설정

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

x

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(처음 + - * / 의 각각의 개수를 입력받아야한다는 조건을 읽고 switch 문을 활용해야겠다고 생각했지만 바로 포기

-> 추후 풀이 추가해보고 싶음)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int N;
int max = -1000000001;
int min = 1000000001;
int num[11];

void calculate(int plus, int minus, int multiplication, int division, int x, int sum)
{
	if (x == N - 1)
	{
		if (max < sum)
		{
			max = sum;
		}
		if (min > sum)
		{
			min = sum;
		}
	}

	else
	{
		if (plus != 0)
		{
			calculate(plus - 1, minus, multiplication, division, x + 1, sum + num[x + 1]);
		}
		if (minus != 0)
		{
			calculate(plus, minus - 1, multiplication, division, x + 1, sum - num[x + 1]);
		}
		if (multiplication != 0)
		{
			calculate(plus, minus, multiplication - 1, division, x + 1, sum * num[x + 1]);
		}
		if (division != 0)
		{
			calculate(plus, minus, multiplication, division - 1, x + 1, sum / num[x + 1]);
		}
	}
}

int main(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &num[i]);
	}

	int plus, minus, multiplication, division;
	scanf("%d %d %d %d", &plus, &minus, &multiplication, &division);
	calculate(plus, minus, multiplication, division, 0, num[0]);

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

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ