BOJ 2529 - 부등호

문제

백준 온라인 저지 - 2529번

풀이 과정

부등호 조건을 만족하는 최소 및 최대 수열을 찾는 문제입니다.

백트래킹 을 활용해서 조건을 만족하는 모든 수열을 생성한 다음 최대 및 최소 값을 비교해서 답을 구하면 됩니다.

코드

import sys

K = int(input())
signs = list(sys.stdin.readline().split())
min_value = '9999999999'
max_value = '0'


def compare(pick):
    global min_value, max_value

    num = ''.join(map(str, pick))
    min_value = min_value if int(min_value) < int(num) else num
    max_value = max_value if int(max_value) > int(num) else num


def dfs(pick, depth):
    if depth == K:
        compare(pick)
        return

    for num in range(10):
        if num not in pick:
            if signs[depth] == '<' and num <= pick[depth]:
                continue
            elif signs[depth] == '>' and num >= pick[depth]:
                continue

            pick.append(num)
            dfs(pick, depth + 1)
            pick.pop()


def solution():
    for start in range(10):
        dfs([start], 0)

    print(max_value)
    print(min_value)


solution()