백준: 16943 숫자 재배치

문제

16943번: 숫자 재배치

 

문제 풀이

 A, B의 숫자가 주어질 때 A의 자릿수로 구할 수 있는 순열을 구하여 B보다 작으면서 가장 큰 값을 반환하는 문제이다. `DFS`를 통해 순열을 구하면서, B보다 작은지 확인하고 최대 값을 갱신해 주면 된다. 중간에 가지치기를 해주고 싶어서, 순열의 처음 값이 B의 첫 번째 값보다 크다면 가지를 뻗지 않게 하려고 했는데... 74~75% 정도에서 `틀렸습니다.` 를 출력한다. 가지치지를 하지 않으니 정답을 맞출 수 있었다.

 

코드

from sys import stdin


def dfs(idx, cur_num):
    global answer

    if idx == length:
        if int(cur_num) <= int(''.join(map(str, b))):
            answer = max(answer, int(cur_num))
        return

    for i in range(length):
        if idx == 0 and a[i] == 0:
            continue

        if not check[i]:
            check[i] = True
            dfs(idx + 1, cur_num + str(a[i]))
            check[i] = False


if __name__ == '__main__':
    answer = -1
    a, b = stdin.readline().split()
    a = list(map(int, a.strip()))
    b = list(map(int, b.strip()))

    length = len(a)
    check = [False] * length
    dfs(0, '')

    print(answer)