BOJ 7490, 0 만들기
ProblemSolving ·이 문제는 재귀호출을 이용한 문제이다.
(재귀함수 문제들을 풀다가 까다롭게 느껴져서 포스팅하면 도움이 될 것 같아서 포스팅했다!)
풀이
공백문자처리만 잘 신경써주면 나머지 부분은 쉽게 구현할 수 있다.
나는 문자를 필요한 만큼 배열에 저장한 다음에 기호의 갯수가 맞으면 기저부분에서 sum이 0이 될 수 있는지 확인한 다음에 출력을 해주었다. 문자가 ‘+’나 ‘-‘이면 단순히 그 부분의 숫자를 더하거나 빼주면 된다. 하지만 ‘ ‘(공백문자)에서는 단순히 처리 할 수 없다. 어떻게 처리해야하나 방황했었지만 찾은 방법은 간단했다. 더하거나 빼줘야할 숫자를 a라는 변수에 저장을 따로해주고 다음 문자를 처리할 때 저장했던 값을 더해주면 된다!
자세한 이해가 필요한 부분은 코드를 보며 이해해보자!
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int t, n;
char arr[22];
void go(int depth)
{
if (depth == n)
{
int sum = 0;
int a = 1; // 처음 숫자는 1이므로 a의 초기값을 1로 설정한다.
for (int i = 2; i <= n; i++)
{
if (arr[i] == ' ') // 다음의 문자도 공백문자일 수도 있으니 a값만 설정해준다.
{
if (a >= 0)
a = 10 * a + i;
else
a = 10 * a - i;
}
if (arr[i] == '+')
{
sum += a;
a = i;
}
if (arr[i] == '-')
{
sum += a;
a = -i;
}
}
sum += a; // 다음 문자를 처리할 때마다 a값을 더해줬으므로 마지막 a값은 따로 더해줘야한다.
if (sum == 0)
{
printf("1");
for (int i = 2; i <= n; i++)
printf("%c%d", arr[i], i);
printf("\n");
}
return;
}
arr[depth + 1] = ' ';
go(depth + 1);
arr[depth + 1] = '+';
go(depth + 1);
arr[depth + 1] = '-';
go(depth + 1);
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
go(1);
printf("\n");
}
return 0;
}