[백준/Baekjoon] 7490 0 만들기 C++ :: Recursion & Back Tracking

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

7490번: 0 만들기

---

1. Logic

- 처음 시작 1은 무조건 양수로 시작한다고 이해하고 풀었다. 왜냐면 -1 -2 +3도 있지만 테케에 포함되지 않기 때문에

 

n = 9일 때를 생각해 보면 처음에 12가 들어오는 경우도 생기기 때문에 1을 먼저 박고 시작하지 않고 0일때를 분할하여 계산해주었다. 

 

부분 문제

1. cnt == 0일때(처음 시작일 때)

 - 1을 더할지

 - 12를 더할지

2. cnt == 0이 아닐때(처음 시작이 아닐때)

 - 한자리만 더할지

 - 한자리만 뺄지

 - 숫자를 이어붙혀 더할지

 - 숫자를 이어붙혀 뺄지

 

조심해야할 점은 출력조건에 아스키 순서에 따라 결과를 출력한다고 되어있다. 그냥 속 편하게 출력 전에 sort해줬다.

---

2. Code

#include<bits/stdc++.h>
#include <string>

using namespace std;

int n;

vector<string> ans;

void solve(int calc, int cnt, string str) {
    if(cnt == n) {
        if(calc == 0) {
            ans.push_back(str);
            return;
        }
        return;
    }

    if(cnt == 0) {
        solve(calc + (cnt+1), cnt+1, str + to_string(cnt + 1));
        solve(calc + (cnt+1)*10 + (cnt+2), cnt + 2, str + to_string(cnt + 1) + ' ' + to_string(cnt + 2));
    }
    else {
        solve(calc + (cnt+1), cnt+1, str + '+' + to_string(cnt + 1));
        solve(calc - (cnt+1), cnt+1, str + '-' + to_string(cnt + 1));
    
        if(cnt + 2 <= n) solve(calc + (cnt+1)*10 + (cnt+2), cnt + 2, str + '+' + to_string(cnt + 1) + ' ' + to_string(cnt + 2));
        if(cnt + 2 <= n) solve(calc - (cnt+1)*10 - (cnt+2), cnt + 2, str + '-' + to_string(cnt + 1) + ' ' + to_string(cnt + 2));
    }
    


}

int main() {
    int t;
    cin >> t;

    while(t--) {
        cin >> n;

        solve(0, 0, "");

        sort(ans.begin(), ans.end());
        
        for(int i = 0; i < ans.size(); i++) {
            cout << ans[i] <<  '\n';
        }
        cout << '\n';

        ans.clear();        
    }
}

 

 

---

 

 

3. Feedback

 - 처음에 조건을 보고 생각할때 아스키 조건을 빼고 구현해서 시간을 좀 잡아 먹었고 두번째로는 처음 시작점에서 1로 시작할지 12로 시작할 지 분할을 안해주고 무작정 1을 알박기하고 시작해서 시간을 오래 잡아먹었다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90