[C/C++] 코드업(codeup) 3540번 0 만들기 게임

▽문제 바로가기

https://codeup.kr/problem.php?id=3540

0 만들기 게임

---

입력

정수 N이 입력된다.( 3 <= N <= 9 )

 

출력

0으로 만드는 모든 수식을 출력한다.

출력 순서는 공백, +, - 순서로 출력한다.

 

문제 풀이

 

완전 탐색 후 합이 0이 되는 모든 수식을 출력해야 합니다.

 

합이 0이 되는지 계산하는 과정이 조금 복잡했습니다. 출력도 해야 하고 계산도 해야 하니...

숫자 외 빈칸, +, - 가 있습니다. 그러나 실질적으로 계산이 이루어지는 연산은 + 와 - 이니 빈칸과 구분해줍니다.

 

+와 -를 만나면 다음 숫자와 연산을 합니다.

다음 숫자는 숫자 다음 공백이 없을 때까지 계산해 줍니다.

 

예를 들어 1 뒤에 공백이 있다면 1에 10을 곱하고 2를 더해서 12를 만듭니다. 또 공백이 있다면 12에 10을 곱해서 3을 더해서 123을 만듭니다.

#include <stdio.h>

using namespace std;

int n;	//입력받을 정수n 
char arr[20];	//출력용 배열

//계산을 위한 숫자
int nextNum(int i){
	int num = i;
	while(arr[(i*2)-1]==' '){
		num = num*10 + i + 1;
		i++;
	}
	return num;
}

//합이 0인지 판별
bool isZero(){
	int sum = nextNum(1);	//초기값
	for(int i=1;i<=n*2-2;i++){
		//실질적인 계산이 일어나는 연산
		if(arr[(i*2)-1]=='+') sum += nextNum(i+1);
		else if(arr[(i*2)-1]=='-') sum -= nextNum(i+1);
	}
	if(sum==0) return true;
	else return false;
}

//백트래킹
void backtracking(int i){
	//완전탐색 끝
	if(i==n){
		//합이 0이면 출력
		if(isZero()){
			for(int i=0;i<=n*2-2;i++){
				printf("%c", arr[i]);
			}
			printf("\n");
		}
		return;
	}
	
	//출력 순서는 공백, +, - 순이므로 탐색을 이 순서로
	arr[(i*2)-1] = ' ';
	backtracking(i+1);
	
	arr[(i*2)-1] = '+';
	backtracking(i+1);
	
	arr[(i*2)-1] = '-';
	backtracking(i+1);
		
}


int main(){
	
	scanf("%d", &n);
	
	//'1', ' ', '2', ' ', ... 으로 초기화
	int one = 49;	//숫자49는 아스키코드 '1' 
	for(int i=0;i<n*2;){
		arr[i] = one;
		one++;
		i+=2;
	}
	
	//백트래킹
	backtracking(1);
	
	return 0;
}