7490: 0 만들기

문제 링크

7490: 0 만들기

구현 방식

• 전형적인 백트래킹 문제
• python으로는 string 형식으로 path를 저장해주고, eval()을 이용해서 한번에 수식의 값을 구해주었다
• cpp로는 vector로 path를 저장해주었고, 매 회마다 result 값도 구해서 저장해주었다
  • 공백 연산의 경우, 앞에 부호가 있는 경우와 없는 경우를 먼저 나눠주었고, 부호가 있다면 그게 '+'인지와 '-'인지로 분기하여 재귀호출 해주었다

코드

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

int N;

void dfs(vector<char> path, int depth, int result){
    if (depth == N-1){
        if (result == 0){
            for (int i=0; i<path.size(); i++){
                cout << path[i];
            }
            cout << '\n';
        }
        return;
    }

    // 공백 연산
    vector<char> p1 = path;
    int n = depth+2;
    p1.push_back(' '); p1.push_back(n+'0');

    if(path.size() > 2){
        int idx = path.size()-2;
        if (path[idx] == '+'){
            dfs(p1, depth+1, result-(n-1)+(10*(n-1)+n));
        }
        else if (path[idx] == '-'){
            dfs(p1, depth+1, result+(n-1)-(10*(n-1)+n));
        }
    }
    else{
        dfs(p1, depth+1, 12);
    }

    // + 연산
    vector<char> p2 = path;
    p2.push_back('+'); p2.push_back(n+'0');
    dfs(p2, depth+1, result+n);

    // - 연산
    vector<char> p3 = path;
    p3.push_back('-'); p3.push_back(n+'0');
    dfs(p3, depth+1, result-n);
}

int main() {
    int T; cin >> T;
    for (int t=0; t<T; t++){
        cin >> N;
        vector<char> tmp; tmp.push_back('1');
        dfs(tmp, 0, 1);
        cout << '\n';
    }
    return 0;
}

import sys

def dfs(path, depth):
    if depth == N-1:
        if check(path): print(path)
        return

    n = depth+2
    dfs(path+' '+str(n), depth+1)
    dfs(path+'+'+str(n), depth+1)
    dfs(path+'-'+str(n), depth+1)

def check(path):
    path = path.replace(' ', '')
    if eval(path) == 0: return True
    else: return False


T = int(sys.stdin.readline()[:-1])
for t in range(T): N = int(sys.stdin.readline()[:-1]); dfs("1", 0); print()