백준 7490번 : 0 만들기 - DFS

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

7490번: 0 만들기

1. 문제 설명

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

 

 

 

 

2. 접근 방법[알고리즘]

 

DFS를 돌면서 +. -. 공백 기호중 하나를 선택하고

 

숫자를 다 사용한 경우, 계산결과가 0이 된다면 출력해준다.

 

 

 

3.문제 풀이 코드 C++

#include <bits/stdc++.h>
using namespace std;

int L;
char path[20];

int cal(){
	int ans=0;
	int cur =0;
	char op='+';
	
	for(int i=0; i<=L; i++){
		if(path[i]=='-'||path[i]=='+'||path[i]=='\0'){
			if(op=='-'){
				ans-=cur;
				cur=0;
			}
			else if(op=='+'){
				ans+=cur;
				cur=0;
			}
			op = path[i];
		}
		else{
			if(path[i]==' '){
				cur*=10;
			}
			else cur += (path[i]-'0');
		}
	
	}

	return ans;
}


void DFS(int cur, int end){
	if(cur==end+1){
		if(cal()==0){
			for(int i=0; path[i]!='\0'; i++){
				printf("%c", path[i]);
			}
			printf("\n");
		}
		
		return;
	}
	else{
		if(cur==end){
			path[L++] = cur+'0';
			DFS(cur+1, end);
			L-=1;
		}
		else{
			
			path[L++] = cur+'0';
			path[L++] = ' ';
			DFS(cur+1, end);
			L-=2;
			
			
			
			path[L++] = cur+'0';
			path[L++] = '+';
			DFS(cur+1, end);
			L-=2;
	
		
			path[L++] = cur+'0';
			path[L++] = '-';
			DFS(cur+1, end);
			L-=2;	
		
		}
	}
	
	
	
}

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t,i,tmp;
	scanf("%d",&t);
	vector<int> input;
	
	for(i=0; i<t; i++){
		int tmp;
		scanf("%d", &tmp);
		input.push_back(tmp);
	}
	
	for(i=0; i<input.size();i++){
		L=0;
		DFS(1, input[i]);
		printf("\n");
	}
	
	
	
}

DFS를 돌면서 계산식을 path에 넣어준다.

 

숫자를 다 사용한 경우에는 cal 함수를 이용해 계산 결과가 0인지 확인 해주고 옳다면 출력해준다.

 

 

 

 

처음에는 DFS를 만들 때 돌면서 바로바로 계산을 해주려 했는데,

 

연산자에 +, - 만 있는게 아니라 공백까지 포함되어, 그럴 경우 계산을 올바르게 하기 힘들다.

 

그래서 아예 숫자를 다 사용한 후에 계산식이 0에 해당하는지 확인하여 출력해주도록 했다.

 

만약에 연산자에 공백이 있는 경우가 아니라면, 매개변수에 결괏값을 넘겨주면서 DFS를 돌면서 계산까지 함께 되도록

 

만들 수 있다.

 

 

그리고 문제 조건 중

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다.

 

이 조건은 DFS를 만들 때

 

맨 처음 공백을 넣어주고 ,+, - 순으로 돌면 해결 된다.

 

만약 이게 헷갈리다면

 

벡터나 배열에 결괏값을 일일이 저장해주고,

 

sort한 후에 하나씩 출력하는 방법도 있다.