[BOJ] 1039 - 교환 (Python)

 

 

아이디어 #1

 

세트를 이용해 연산을 K번 수행했을 때 나올 수 있는 수의 최댓값을 구한다.

 

 

풀이 #1

 

def solution():
    N, K = input().split()
    K = int(K)
    M = len(N)
    numbers = [set() for _ in range(K+1)]
    numbers[0].add(N)
    for k in range(K):
        for number in numbers[k]:
            num = [*number]
            for i in range(M-1):
                for j in range(i+1, M):
                    if i == 0 and num[j] == '0':
                        continue
                    num[i], num[j] = num[j], num[i]
                    numbers[k+1].add(''.join(num))
                    num[i], num[j] = num[j], num[i]
    if numbers[-1]:
        print(max(map(int, numbers[-1])))
    else:
        print(-1)

solution()

 

 

 

아이디어 #2

 

DFS로 연산을 K번 수행했을 때 나올 수 있는 수의 최댓값을 구한다.

 

 

풀이 #2

 

def dfs(idx, cnt):
    global res
    if cnt >= K:
        _num = int(''.join(num))
        if _num > res:
            res = _num
        return
    if idx >= M-2:
        if (K-cnt)%2:
            num[-1], num[-2] = num[-2], num[-1]
            dfs(idx, K)
            num[-1], num[-2] = num[-2], num[-1]
        else:
            dfs(idx, K)
        return
    dfs(idx+1, cnt)
    for j in range(idx+1, M):
        num[idx], num[j] = num[j], num[idx]
        dfs(idx+1, cnt+1)
        num[idx], num[j] = num[j], num[idx]

N, K = input().split()
K = int(K)
M = len(N)
res = -1
num = [*N]
if M == 1 or (M == 2 and num[-1] == '0'):
    print(-1)
else:
    dfs(0, 0)
    print(res)