백준 7490 - 0 만들기

문제 설명

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 1부터 N까지 연속한 수열의 사이에 연산자를 추가하여 0을 만들 수 있는 경우를 출력하는 것이다.

이때, 연산자는 총 3개이다.

• +: 더하기
• -: 빼기
• ' ': 이어 붙이기

 

해당 문제는 dfs(재귀)를 통해 해결할 수 있다.

+와 -만으로 이루어진 식은 간단하지만 문제는 ' '(공백)을 처리하는 것이다.

공백이 까다로운 이유는 공백 연산이 있으면 바로바로 연산을 처리할 수 없기 때문이다.

예를 들어, 식이 1+2 3-4이라고 가정해 보자.

1+2를 진행한 뒤 공백 연산자를 만나면 이전에 2를 더한 연산이 올바르게 적용되지 않은 것이다.

2가 아니라 23을 더해야 하기 때문이다.

즉, 연산자의 우선순위가 공백 연산자가 앞선다.

 

이를 해결하는 트릭은 2가지 이다.

• 연산자를 트래킹 하기 위해 스트링을 사용하는 것
• 바로바로 계산하지 않는 것

우선 첫 번째는, 출력으로 모든 숫자와 연산자를 출력해야 한다.

즉, 현재까지 이뤄진 연산자를 모두 저장하여 출력해야 한다는 뜻이다.

이를 스트링을 통해 숫자와 연산자를 합쳐 결과 스트링을 유지하며 진행하다 0을 만들 수 있다면 출력하면 된다.

 

두 번째는 바로바로 계산하지 않는 것이다.

그렇다면 언제 계산을 해야 하나 생각이 들 것이다.

정답은 공백 연산자가 아닐 때 계산하는 것이다.

앞에서 설명한 공백 연산자가 까다로운 이유는 이전 연산이 올바르게 적용되지 않기 때문이라 설명했다.

이를 해결하기 위해, 공백 연산자를 만나면 계산해야 할 수를 저장하다 '+'나 '-'연산자를 만나면 계산하면 된다.

1+2 3-4일 때, 2와 3 사이에 공백 연산자를 처리하기 위해 아무것도 하지 않는 것이다.

정확히 말하면 다음에 연산자에게 처리할 값을 추가해 주는 것이다.

2를 23으로 바꿔준다는 뜻이다.

이후, -를 만나면 23을 빼준다.

즉, 나중에 계산할 버퍼를 만든다고 생각하면 된다.

 

마지막 수에 도착하면 버퍼에 있는 수를 더해주고 계산 결과가 0이라면 스트링을 출력한다.

void DFS(int sum, int num, int depth, string str)
{
    if (depth == N+1)
    {
        sum += num;
        if (sum == 0)
        {
            cout << str << '\n';
        }

        return;
    }

    if (num < 0) DFS(sum, num * 10 - depth, depth + 1, str + " " + char(depth + '0'));
    else DFS(sum, num * 10 + depth, depth + 1, str + " " + char(depth + '0'));
    
    DFS(sum + num, depth, depth + 1, str + "+" + char(depth + '0'));
    DFS(sum + num, -depth, depth + 1, str + "-" + char(depth + '0'));
}

 num: 임시 버퍼

depth: 실제 수

 

정리하자면, 공백 연산은 num을 늘려나가고 +나 -를 만나면 늘려놓은 num을 계산한 뒤 num을 갱신한다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int T, N;

void DFS(int sum, int num, int depth, string str)
{
    if (depth == N+1)
    {
        sum += num;
        if (sum == 0)
        {
            cout << str << '\n';
        }

        return;
    }

    if (num < 0) DFS(sum, num * 10 - depth, depth + 1, str + " " + char(depth + '0'));
    else DFS(sum, num * 10 + depth, depth + 1, str + " " + char(depth + '0'));
    
    DFS(sum + num, depth, depth + 1, str + "+" + char(depth + '0'));
    DFS(sum + num, -depth, depth + 1, str + "-" + char(depth + '0'));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

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


    return 0;
}

---