백준 7490 c++ "0 만들기" -PlusUltraCode-

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

[필자 사고]

재미난 문제다. DFS를 이용하여 풀었다.

idx와 expr을 dfs매개변수로 받고 각 경우의 맞게 Ascll 코드 오름차순 형태로 탐색을 진행했따.

만약 N값 보다 idx가 크게 되는 경우 이제 계산할 차례다.

각 char ch : expr 에서 부호들을 찾을 경우 numStr의 값을 nums백터에 넣고 부호 벡터에 넣는 형태로 구한다.

numStr을 "" 로 초기화하는거 잊지 말자.

다음으로 공백은 무시하자 만약 문자열을 만나게 되면 numStr+=ch 형태로 만들면 된다.

 

이제 nums배열에 넣은 숫자들과 ops배열에 넣은 부호들을 이용하여 계산에 진행하자.

미리 처음 숫자 int  result = nums[0]을 받은 뒤

각 부호에 맞게 계산을 진행하자.

 

만약 result ==0 이라면 성공

 

아래는 자세한 코드 해설이다.

[코드 해설]

dfs(int idx, string expr)

• 백트래킹(DFS)으로 식을 생성하는 함수이다.
• 매개변수:
  • idx: 현재 붙일 숫자
  • expr: 지금까지 만든 수식 문자열
• 동작 과정:
  1. idx > N일 경우 → 모든 숫자가 다 붙었으므로 완성된 수식을 평가한다.
     • 문자열을 순회하며 숫자와 연산자를 분리한다.
       • '+' 또는 '-'가 나오면 지금까지 누적된 숫자를 정수로 변환하여 nums에 저장하고, 연산자를 ops에 넣는다.
       • ' '은 무시하고, 나머지 숫자는 문자열로 이어 붙인다.
     • 마지막 남은 숫자도 정수로 변환해 nums에 추가한다.
     • 계산 단계에서는 nums[0]을 시작값으로 두고, ops를 순서대로 적용해 결과를 구한다.
     • 최종 결과가 0이면 해당 식을 출력한다.
  2. idx <= N일 경우 → 다음 숫자를 붙이는 세 가지 선택을 모두 탐색한다.
     • 숫자 앞에 ' '을 붙이는 경우 (즉, 숫자 이어붙이기)
     • 숫자 앞에 '+'를 붙이는 경우
     • 숫자 앞에 '-'를 붙이는 경우

---

main()

• 입출력 최적화를 설정한다.
• 테스트 케이스 개수를 입력받는다.
• 각 테스트 케이스마다 N을 입력받은 후,
  • dfs(2, "1")을 호출해 1에서 시작하는 수식을 만든다.
  • 한 테스트 케이스 결과가 끝나면 빈 줄을 출력해 구분한다.

---

전체 흐름

1. 입력으로 주어진 N에 대해 1부터 N까지의 수열을 만든다.
2. DFS로 모든 가능한 식을 만들어 본다. (공백, 더하기, 빼기)
3. 완성된 식을 직접 계산한다.
4. 값이 0인 식만 출력한다.
5. 각 테스트 케이스 결과 사이에는 공백 줄을 둔다.

[소스 코드]

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int N;

void dfs(int idx, string expr) {
   
    if (idx > N) {
        string numStr = "";
        vector<int> nums;
        vector<char> ops;

        for (char c : expr) {
            if (c == '+' || c == '-') {
                ops.push_back(c);
                nums.push_back(stoi(numStr));
                numStr = "";
            }
            else if (c != ' ') {
                numStr += c;
            }

         
        }
        nums.push_back(stoi(numStr));


        int result = nums[0];
        for (int i = 0; i < ops.size(); i++) {
            if (ops[i] == '+')result += nums[i + 1];
            else result -= nums[i + 1];

        }
        if (result == 0) cout << expr << "\n";


        return;
    }
    dfs(idx + 1, expr + " " + to_string(idx)); // 공백
    dfs(idx + 1, expr + "+" + to_string(idx)); // +
    dfs(idx + 1, expr + "-" + to_string(idx)); // -
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> N;
        dfs(2, "1");
        cout << "\n"; 
    }
    return 0;
}