코딩 테스트 준비! (백준)/DFS

[DFS] 백준 1248번 Guess(C++)

lee-soo 2025. 4. 14. 18:38

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

 

영어를 보니 현기증이 난다.

내용 자체는 생각보다 간단하다

 

해당 조건을 만족하는 수열을 찾아라!

 

1.n입력

2.부호입력

3.해당 부호에 맞는 수열 입력

 

해당 부호는

 

예를들어 수열이 3 -6 2 7일 경우

 

앞에서부터 하나씩 더한 값의 부호를 정하는 것이다.

 

ex)

 

3 = 3 +

3 - 6 = -3 -

3-6+2 = -1 -

3-6+2+7 = 6 +

즉 +--+ 이렇게나오고

그 다음은

맨 앞 수를 제외한 나머지도 똑같이 진행

 

-6 =-6 -

-6 +2 = -4 -

-6+2+7 = 3 +

- - +

...

 

이렇게 진행해 나가는 것인데

 

이것을 처음 입력단에 쓴 후 적절한 수열 아무거나 출력하라는 뜻이다.

 

예를들어 4 +--+--++++ 이렇게 되어있다면 

앞서 말한 수열 3 -6 2 7 이 나오는 것

 

그렇다면 진행을 어떻게 해야될까?

 

먼저 수열 여러개를 택한 브루트 포스인걸 알겠으나 

모든 방법을 고려하면 아마 시간초과가 뜰 것이다.

 

왜냐면 10CN번을 다돌리면 진짜 많거든...

 

먼저 시간초과가 뜬 나의 코드를 보여주겠따

 

 

---

#include <iostream>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
bool visited[20];
int n;
char arr[10][10];
vector<int> v;
char s[10][10];
void task(int depth);
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
        {
            cin >> s[i][j];
        }

    task(0);
}
void task(int depth)
{
    if (depth == n)
    {

        for (int i = 0; i < n; i++)
        {
            int temp_sum = 0;
            for (int j = i; j < n; j++)
            {
                temp_sum += v[j];
                if (s[i][j] == '+' && temp_sum <= 0)
                    return;
                if (s[i][j] == '-' && temp_sum >= 0)
                    return;
                if (s[i][j] == '0' && temp_sum != 0)
                    return;
            }
        }

        for (int i = 0; i < n; i++)
            cout << v[i] << " ";
        cout << "\n";
        exit(0);
    }

    for (int i = -10; i <= 10; i++)
    {
        v.push_back(i);
        task(depth + 1);
        v.pop_back();
    }
}
 
해당 방법의 경우 중복을 피하라는 말은 없었다.
 
그래서 이제 그냥 내부에서 모든 수열을 더해주는 방식만 생각하면 된다.

        
for (int i = 0; i < n; i++)
        {
            int temp_sum = 0;
            for (int j = i; j < n; j++)
            {
                temp_sum += v[j];
                if (s[i][j] == '+' && temp_sum <= 0)
                    return;
                if (s[i][j] == '-' && temp_sum >= 0)
                    return;
                if (s[i][j] == '0' && temp_sum != 0)
                    return;
            }
        }
 
depth==n일때, 해당 방벙으로 진행하게되면
0, 0+1,0+1+2. 방법으로 계속 더해나갈 수 있다.
처음에 나는 저 s[i][j]와 +를 비교하려면 2가지 반복문을 모두 지난 후 더해야 된다 생각해서 오래걸렸다.
하지만 이렇게 앞에서부터 진행하면, 첫번째원소만을 더한값 , 첫번째원소 + 두번째원소.. 이렇게 차례차례 지나가며 i가 2로가면 다시 j=1부터 더해지는 방식을 깨달았다.
 
그래서결과는

오우 노우

대체 문제가 뭐야

 

앞서말한 시간초과의 문제의 위험성이였다.

 

사실 이 식은 depth==n이될때가지, 정말 수많은 가짓수를 거치며 ( 20개의 수 중에서 n개의 수열을 고름 )

최대 20C10 가지의 수를 찾아볼 수 있기 때문에 

최악의 경우 백만가지 이상의 경우의 수를 돌 수 있다.

 

그렇다면 ?

how do i do?

 

저 중간에 보이는 조건문을 따로 빼주어, 수열을 정할 때, 조건에 맞지 않다면 바로 return해주는 것이다.

 

#include <iostream>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
bool visited[20];
int n;
char arr[10][10];
vector<int> v;
char s[10][10];
void task(int depth);
bool isValid(int depth)
{
    int sum = 0;
    for (int i = depth; i >= 0; i--)
    {
        sum += v[i];
        if (s[i][depth] == '+' && sum <= 0)
            return false;
        if (s[i][depth] == '-' && sum >= 0)
            return false;
        if (s[i][depth] == '0' && sum != 0)
            return false;
    }
    return true;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
        {
            cin >> s[i][j];
        }

    task(0);
}
void task(int depth)
{
    if (depth == n)
    {
        for (int i = 0; i < n; i++)
            cout << v[i] << " ";
        cout << "\n";
        exit(0);
    }

    for (int i = -10; i <= 10; i++)
    {
        v.push_back(i);
        if (isValid(depth))
            task(depth + 1);
        v.pop_back();
    }
}
이렇게 모든 수열을 구하는 백트래킹 과정에서, isValid인지 미리 구하는 것을 하면, 적절하지 않은 답들은 사전에 처리되어 무사히 통과할 수 있다.

짜잔