[SWEA] D3. 최대 상금

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD

SW Expert Academy

 

 

1. 해결 방법

swea에서 D3 치고는 어려웠던 문제이다.

완전탐색 문제이며, 가지치기를 하지 않으면 시간초과가 나온다,,
해결하는데 1시간 조금 넘게 걸렸다. 가지치기 경우를 생각하는데 있어서 시간이 오래걸린듯 하다.

숫자들의 자리를 서로 교환해야하는 문제인데
재귀함수를 이용해서 2중 for문에 해당하는 i, j를 이용하여 자릿수를 바꿔주고 재귀함수를 넣어준다.

가지치키 경우에는 answer를 2차원 배열로 두어서 교환 횟수 값에 해당하는 인덱스 위치의 값을 max() 메서드를 이용하여 주어진 횟수만큼 자릿수 교체가 이루어진 숫자들이 append 되어있으므로, 그 값 중에서 최댓값을 가져오면 된다.

 

 

2. 정답코드

T = int(input())

# dfs
def dfs(numbers, depth):
    global answer, max_v

    temp = ''
    for number in numbers:
        temp += number

    # 가지치기
    if int(temp) in answer[depth]:
        return
    else:
        answer[depth].append(int(temp))

    if depth == m:
        return

    len_n = len(numbers)
    for i in range(len_n):
        for j in range(i + 1, len_n):
            numbers[i], numbers[j] = numbers[j], numbers[i]
            dfs(numbers, depth + 1)
            numbers[i], numbers[j] = numbers[j], numbers[i]


# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    n, m = map(int, input().split())

    numbers = list(str(n))
    answer = [[] for _ in range(m + 1)]
    max_v = n
    dfs(numbers, 0)
    print(f'#{test_case} {max(answer[m])}')