[C/C++] 백준 #2529 부등호(탐욕 알고리즘)

이번 문제는 백트래킹(back tracking) 기법을 사용하면 편하게 풀 수 있는 문제입니다.  큰 수의 경우에는 9부터 원하는 개수만큼, 작은 수의 경우에는 0부터 원하는 개수만큼 선택해서 그것으로 백트래킹을 하면 됩니다.

 

less or larger

 

저는 조금 다른 식으로 풀어보았습니다.

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

2529번: 부등호

바로 탐욕 알고리즘을 이용해서 큰 수가 들어가야할 위치를 찾는 것이죠.

예를 들어서 (1) < (2) < (3) > (4) ... 형태로 시작한다면, (3)에 가장 큰 수인 9를 (2)에 그 다음 큰 수인 8을 (1)에 그 다음 큰 수인 7을 배치하는 것이죠.  이렇게 하면 모든 수를 다 돌아보지 않아도 됩니다.  백트래킹 알고리즘을 이용한다면, \(O(N!)\) 이 들 수 있지만, 사실 10개 다 돌려보았자 10! 수가 몇백만밖에 안 되고, 백트래킹 알고리즘의 특성상 중간에 뒤돌아가는 횟수가 많기 때문에 시간복잡도 상 팩토리얼(factorial) 알고리즘이라도 시간이 많이 짧아지지는 않습니다.

 

제가 작성한 소스입니다.  백트래킹을 사용했다면 훨씬 소스가 간단했겠지만, 다소 복잡합니다.

//------------------------------------------------
//    baekjoon #2529
//        - by Aubrey Choi
//        - created at 2019-07-10
//------------------------------------------------
#include <stdio.h>

int main()
{
    int v[11][2] = {0, }, k, r1[11] = {0, }, r2[11] = {0, };
    char str[2], prev, ans[11], s;
    scanf("%d%s", &k, str);
    if(str[0] == '<') v[1][0] = 2, r1[2]++, r2[2]++;
    prev = str[0];
    for(int i = 2; i <= k; i++)
    {
        scanf("%s", str);
        int t = 0;
        if(prev == '>') v[i][t++] = i - 1, r1[i - 1]++, r2[i - 1]++;
        if(str[0] == '<') v[i][t++] = i + 1, r1[i + 1]++, r2[i + 1]++;
        prev = str[0];
    }
    if(prev == '>') v[k+1][0] = k, r1[k]++, r2[k]++;
    s = '9'-k, ans[k + 1] = 0;
    for(int i = 0; i < k + 1; i++)
    {
        int t;
        for(t = k+1; t >= 1; t--)
            if(r1[t] == 0) break;
        r1[t] = -1;
        ans[t - 1] = s++;
        r1[v[t][0]]--;
        r1[v[t][1]]--;
    }
    puts(ans);
    s = '0', ans[k+1] = 0;
    for(int i = 0; i < k + 1; i++)
    {
        int t;
        for(t = 1; t <= k + 1; t++)
            if(r2[t] == 0) break;
        r2[t] = -1;
        ans[t - 1] = s++;
        r2[v[t][0]]--;
        r2[v[t][1]]--;
    }
    puts(ans);
    return 0;
}