[BOJ][C#] 2529 부등호

📕 문제

📌링크

📗 접근

• 서로 다른 숫자(0~9) 중 K+1개로 부등호 K개를 만족하는 수열 구성
• 백트래킹: 자리(depth)별 숫자 선택 → 사용 여부 체크
• 이전 자리와 현재 자리의 부등호 만족 시에만 진행
• 완성 시 문자열 사전식 비교로 maxAns, minAns 갱신 (길이 K+1 고정)

복잡도: 최악 P(10, K+1). 앞자리 0 허용.

📘 코드

using System;
using System.IO;

public class BOJ
{
    // https://www.acmicpc.net/problem/2529

    static readonly int[] nums = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    static readonly bool[] used = new bool[nums.Length];

    static int K;
    static string[] ops;
    static char[] selected;
    static string maxAns = "";
    static string minAns = "";
    static bool IsValid(int a, int b, string op) => op == "<" ? a < b : a > b;

    public static void Main()
    {
        using var sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        using var sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

        int k = int.Parse(sr.ReadLine());
        string s = sr.ReadLine();

        K = k;
        ops = s.Split();
        selected = new char[K + 1];

        Dfs(0);

        sw.WriteLine(maxAns);
        sw.WriteLine(minAns);
    }

    static void Dfs(int depth)
    {
        if (depth == K + 1)
        {
            string number = new string(selected, 0, K + 1);
            if (maxAns == "" || string.CompareOrdinal(number, maxAns) > 0) maxAns = number;
            if (minAns == "" || string.CompareOrdinal(number, minAns) < 0) minAns = number;
            return;
        }

        for (int i = 0; i < nums.Length; i++)
        {
            if (used[i]) continue;

            if (depth == 0 || IsValid(selected[depth - 1] - '0', i, ops[depth - 1]))
            {
                used[i] = true;
                selected[depth] = (char)('0' + i);
                Dfs(depth + 1);
                used[i] = false;
            }
        }
    }
}

📒 알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

📙 오답노트