[boj][c++] 2529 부등호

2529 부등호

내가 생각했던 백트래킹 표준 그 잡채인 문제였다.

• 답이 나왔을 때 : 문자열을 벡터에 저장함
• 다음 경우
  • index가 0이면 일단 문자열에 붙임
  • 부등호 비교하여 알맞은 수이면 문자열에 붙임

문제를 대충 읽어서 제대로 접근했는데도 한참동안 답이 왜 저런지 고민했다. (맞왜틀)

위의 로직을 수행한 뒤에 벡터를 정렬하고 가장 큰 값과 가장 작은 값만 출력하면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int k;
char updown[10];
bool check[10];
vector<string> ans;

bool ok(int pre, int now, char x)
{
    if (x == '<')
    {
        if (pre < now)
            return true;
    }
    if (x == '>')
        if (pre > now)
            return true;
    return false;
}

void go(int index, string s)
{
    if (index == k + 1)
    {
        ans.push_back(s);
        return;
    }
    for (int i = 0; i <= 9; i++)
    {
        if (check[i] == true)
            continue;
        if (index == 0 || ok(s[index - 1], i + '0', updown[index - 1]) == true)
        {
            check[i] = true;
            go(index + 1, s + to_string(i));
            check[i] = false;
        }
    }
}

int main()
{
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> updown[i];
    }
    go(0, "");
    sort(ans.begin(), ans.end());
    cout << ans.back() << '\n';
    cout << ans.front() << '\n';
    return 0;
}

인강

알고리즘 강의 듣는게 의외로 동기부여가 된다. 미쳐 날뛰는 백준 선생님의 진도를 따라잡으려고 하루에 두세문제씩 꾸준히 풀게 된다. 하루 한 문제 겨우 해결하던 전과는 사뭇 다른 느낌. 시간 끝나가는게 더 아까워서 그런걸지두ㅇㅅㅇ