[DFS] 백준 2529번 부등호(C++)

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

 

이 문제!!

백트래킹!

 

모든 경우의수 찾아보자고

 

대충 문제는 이해가 갈 것이다

 

1.각 부등호 사이사이에 들어갈 수 있는 적절한 수열을 찾아 넣으시오

2.단 중복되면 안됨

 

어떻게??

 

나의 생각은

 

1.각 부등호 사이에 들어갈 수 있는 후보군 수열을 찾아놓는다

2.그 후 실제로 부합한지 부등호에 맞게 검사(조건문) 아니면 return

 

우선 이렇게만 해도 대충 수열은 나올 것이고

 

이후, 나온 값들에 대한 최대 최소를 구해야되는데

무작정 숫자로 바꿧다간, 012 의 경우 12로 출력되는 불상사가 발생할 수 있기에 출력또한 string 이나 char을 사용해야 한다.

 

#include <iostream>

#include <cmath>

#include <vector>

#include <string>

using namespace std;

bool visited[10];

int n;

string max_s, min_s;

long long maxx = 0, minn = 100000000000;

vector<long> v;

char s[9];

void task(int depth);

int main()

{

    cin >> n;

    for (int i = 0; i < n; i++)

        cin >> s[i];

    task(0);

    cout << max_s << "\n"

         << min_s << "\n";

}

void task(int depth)

{

    if (depth == n + 1)

    {

        for (int i = 1; i < n + 1; i++)

        {

            if (s[i - 1] == '>' && !(v[i - 1] > v[i]))

                return;

            if (s[i - 1] == '<' && !(v[i - 1] < v[i]))

                return;

        }

        int sum = 0;

        string temp;

        for (int i = 0; i < n + 1; i++)

            temp.append(to_string(v[i]));

        if (stoll(temp) > maxx)

        {

            max_s = temp;

            maxx = stoll(temp);

        }

        if (stoll(temp) < minn)

        {

            min_s = temp;

            minn = stoll(temp);

        }

        return;

    }

    for (int i = 0; i <= 9; i++)

    {

        if (!visited[i])

        {

            visited[i] = true;

            v.push_back(i);

            task(depth + 1);

            v.pop_back();

            visited[i] = false;

        }

    }

}

 

대충 흐름 자체는 앞서 정말 많이했던 수열문제와 유사하다.

 

이 문제는 수열 문제를 푸는 방법만 안다면 쉽다!

 

모른다면

https://lee-soo.tistory.com/17

[DFS] 백준 15649번 N과 M (1,2,3) (C++)

n,m 시리즈를 한번 보고 오길 추천!