0 만들기

이번 글은 숫자 수열에서 "+", "-", "공백"을 활용하여 전체 계산 결과가 0이 되도록 만드는 문제를 해결해보려고 합니다. 이 문제를 풀기 위해 작성한 코드와 함께 문제 해결 과정을 살펴보겠습니다.

---

문제 설명
주어진 수열에 숫자 사이에 "+", "-", "공백"을 삽입하여 전체 계산 결과가 0이 되도록 만들어야 합니다. 단, 첫 번째 숫자 앞에는 연산자를 넣을 수 없으며, 공백은 이전 숫자와 연결된 숫자로 처리됩니다. 예를 들어, "2 3"이면 23으로 처리됩니다.

입력과 출력
입력으로는 정수 N이 주어지며, 출력으로는 0을 만들 수 있는 모든 수식을 출력해야 합니다. 출력은 공백, "+", "-" 순서로 출력되어야 합니다.

예시
입력: 7

출력:
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

---

순서도

 

1. 문자열 변수 s와 정수 변수 d 선언
2. 함수 f
   2.1. 정수 변수 a를 매개변수로 받음
   2.2. 정수 변수 p를 a로 초기화
   2.3. s 배열의 ((a * 2) - 1) 인덱스 값이 빈 칸일 때까지 반복
   2.3.1. p에 (p * 10) + a + 1을 할당
   2.3.2. a를 증가시킴
   2.4. p 반환
3. 함수 f2
   3.1. 정수 변수 a를 f(1)로 초기화
   3.2. 1부터 (d * 2 - 1)까지 반복
   3.2.1. 만약 s 배열의 ((i * 2) - 1) 인덱스 값이 +이면
   3.2.1.1. a에 f(i + 1)을 더함
   3.2.2. 만약 s 배열의 ((i * 2) - 1) 인덱스 값이 -이면
   3.2.2.1. a에서 f(i + 1)을 뺌
   3.3. 만약 a가 0이면
   3.3.1. 1 반환
   3.4. 그렇지 않으면
   3.4.1. 0 반환
4. 함수 f3
   4.1. 정수 변수 a를 매개변수로 받음
   4.2. 만약 a가 d와 같다면
   4.2.1. 만약 f2()가 1이면
   4.2.1.1. s 배열의 모든 요소 출력
   4.2.2. 반환
   4.3. s 배열의 ((a * 2) - 1) 인덱스 값을 빈 칸으로 설정
   4.4. f3(a + 1) 호출
   4.5. s 배열의 ((a * 2) - 1) 인덱스 값을 +로 설정
   4.6. f3(a + 1) 호출
   4.7. s 배열의 ((a * 2) - 1) 인덱스 값을 -로 설정
   4.8. f3(a + 1) 호출
5. main 함수
   5.1. d입력
   5.2. s 초기화
   5.3. d * 2번 반복

---

코드 분석

#include <stdio.h>

char s[20];
int d;

// a부터 시작하여 빈 칸이 나오기 전까지 숫자를 이어 붙이는 함수
int f(int a) {
   int p = a;
   while (s[(a * 2) - 1] == ' ') {
      p = p * 10 + a + 1;
      a++;
   }
   return p;
}

// 0인지 확인하는 함수
int f2() {
   int a = f(1);
   for (int i = 1; i < d * 2 - 1; i++) {
      if (s[(i * 2) - 1] == '+')
         a += f(i + 1);
      else if (s[(i * 2) - 1] == '-')
         a -= f(i + 1);
   }
   if (a == 0)
      return 1;  // 1 반환
   else
      return 0;  // 0 반환
}

// 수식을 생성, 출력
void f3(int a) {
   if (a == d) {
      if (f2() == 1) {
         for (int i = 0; i < d * 2 - 1; i++)
            printf("%c", s[i]);
         puts("");
      }
      return;
   }
   s[(a * 2) - 1] = ' ';
   f3(a + 1);
   s[(a * 2) - 1] = '+';
   f3(a + 1);
   s[(a * 2) - 1] = '-';
   f3(a + 1);
}

int main() {
   int k = 49;  // 아스키 코드 값 49 = '1'
   scanf("%d", &d);  // 숫자의 개수

   // 수식 문자열 초기화
   for (int i = 0; i < d * 2;) {
      s[i] = k;
      k++;
      i += 2;
   }

   f3(1);  // 수식 생성, 출력

   return 0;
}

코드 설명
이 코드는 입력받은 수 N을 기반으로 숫자 수열을 생성하고, 모든 가능한 조합을 시도하여 0을 만드는 수식을 찾아냅니다. 다음은 코드의 주요 함수입니당

1. f  : 인덱스 a를 시작으로 공백이 나오기 전까지의 숫자를 합쳐서 반환. 공백은 이전 숫자와 연결된 숫자로 처리.
2. f2 : 숫자 수열을 기반으로 계산을 수행하고, 결과가 0인지 확인. 결과가 0이면 1을 반환하고, 그렇지 않으면 0을 반환.
3. f3 : 재귀 함수, 인덱스 a를 기준으로 공백, "+", "-"를 순차적으로 삽입하며 가능한 모든 수식을 탐색. a가 d와 같아지면 모든 수식을 완성한 것이므로 f2 함수를 호출, 0인 경우 출력.
4. main : 수열을 생성, f3 함수 호출

---

실행화면

실행화면