[재귀함수] BAEKJOON ' 7490 '번 '0 만들기 '문제 (C++/python)

문제 : www.acmicpc.net/problem/7490

7490번: 0 만들기

 

 

 

• 문제 해결 아이디어

    1.  주어지는 자연수가 3이상 9 이하로 적은 수 이므로, 완전 탐색을 사용한다.

   

    2.  정답을 저장 할 배열을 선언하고, 조건(연산 결과가 0)이 만족하면, 값을 출력 또는 저장한다.

   

 

 

• python

연산자만을 저장하는 배열과 수를 저장하는 배열을 따로 선언한다.

연산자를 이용한 모든 경우의 수를 찾고, 숫자 사이사이에 대입해 결과를 모두 계산한다.

숫자 사이에 연산자 대입

 

n = 3일 때, 모든 경우의 수

 

import copy

def recursive(arr, n):                          # 연산자가 가질 수 있는 모든 경우의수
    if len(arr) == n:
        operators.append(copy.deepcopy(arr))    # operator list에 arr내용을 복사하여 넣는다.
        return
    arr.append(' ')
    recursive(arr, n)
    arr.pop()

    arr.append('+')
    recursive(arr, n)
    arr.pop()

    arr.append('-')
    recursive(arr, n)
    arr.pop()

test_case = int(input())

for _ in range(test_case):
    operators = []
    n = int(input())
    recursive([], n-1)

    all_int = [i for i in range(1, n+1)]        # 1 ~ n 수 저장

    for operator in operators:
        string = ""                             # string에 연산식을 저장한다.
        for i in range(n-1):
            string += str(all_int[i]) + operator[i]
        string += str(all_int[-1])
        if eval(string.replace(" ", "")) == 0:  # eval함수를 사용하여 연산식을 바로 계산한다.
            print(string)                       # 연산 결과가 0이면 식을 출력한다.
    print()

 

• c++

계산 결과값 (result)과 그 내용을 계속 다음 단계로 넘기고, 마지막 단계에 result값이 0이라면 그 내용을 출력해준다.

#include "iostream"
#include "cstdlib"
#include "vector"

using namespace std;

int N;

void calculate(int n, int result, vector<char> v){
        
    if(n == N){                              // 입력한 값까지 모두 확인
        if(result == 0){                     // 그때의 result가 0이라면 출력
            for(int i=0 ; i< v.size() ; i++){
                printf("%c",v[i]);
            }
            printf("\n");
        }
        return;
    }
    
    // 공백 연산자
    vector<char> v1 = v;
    v1.push_back(' ');
    v1.push_back(n +1 +'0');                 // int형인 n+1을 char형으로 바꾸는 방법
    int result_space = result;
    if(v.size() > 2){                        // 입력받은 v의 크기가 2보다 작으면 처음 1만 입력됐을 때이다.
        int tmp = v.size()-2;                // 현재 수의 부호를 담고있는 index를 저장한다.
        if(v[tmp] == '+'){                   // 현재 수가 양수일 경우
            result_space = result- n + (10*n + (n+1));
            calculate(n+1, result_space, v1);
        }
        else if(v[tmp] == '-'){              // 현재 수가 음수일 경우
            result_space = result+ n - (10*n + (n+1));
            calculate(n+1, result_space, v1);
        }
    }
    else{                                    // 현재 수가 1이므로, result로 12를 넘겨준다.
        calculate(n+1, 12, v1);
    }
    
    // '+' 연산자
    vector<char> v2 = v;
    v2.push_back('+');
    v2.push_back(n +1 +'0');
    calculate(n+1, result + n+1, v2);
  
    // '-' 연산자
    vector<char> v3 = v;
    v3.push_back('-');
    v3.push_back(n +1 +'0');
    calculate(n+1, result - n-1, v3);
}


int main(){
    
    int test_case;
    scanf("%d",&test_case);
    
    while(test_case){
        scanf("%d",&N);
        vector<char> v;
        v.push_back('1');
        
        calculate(1, 1, v);                   // 초기에 1을 넣어두고 시작한다.
        printf("\n");
        
        test_case--;
    }

    
    return 0;
}

ASCII순서대로 출력하기 위해서, 공백 연산자를 가장 먼저 수행하고, 그 다음 '+', '-'를 차례로 수행한다.

char형 vector에 int를 넣기 위하여 push_back시 '0'을 더해준다.