문제 설명
•
숫자판에서 두 자리를 정해진 횟수만큼 교환하여 최대한 큰 금액을 얻는 문제
◦
반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.
예제 입력/출력
•
입력1
3
123 1
2737 1
32888 2
Plain Text
복사
•
출력1
#1 321
#2 7732
#3 88832
Plain Text
복사
제약 조건
•
•
숫자판의 최대 자릿수는 6자리이며, 최대 교환 횟수는 10
문제 풀이
풀이1 브루트 포스
풀이 코드
def dfs(depth):
global ans
if depth == M:
ans = max(ans, int(''.join(arr)))
return
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
arr[i], arr[j] = arr[j], arr[i]
check = int(''.join(arr))
if (depth, check) not in visited:
visited.append((depth, check))
dfs(depth + 1)
arr[i], arr[j] = arr[j], arr[i]
result = []
T = int(input())
for case in range(1, T + 1):
N, M = map(int, input().split())
arr = list(str(N))
visited = []
ans = 0
dfs(0)
print(f"#{case} {ans}")
Python
복사
