SWEA 1244번: 최대 상금 (D3) - Python 풀이

문제 설명

SW Expert Academy

퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다.

우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다.

예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자.

교환전>

처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다.

다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다.

정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다.

숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다.

위의 예에서와 같이 최종적으로 숫자판들이 8,8,8,3,2의 순서가 되면 88832원의 보너스 상금을 획득한다.

여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.

다음과 같은 경우 1회의 교환 횟수가 주어졌을 때 반드시 1회 교환을 수행하므로 결과값은 49가 된다.

94의 경우 2회 교환하게 되면 원래의 94가 된다.

정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.

[입력]

가장 첫 줄은 전체 테스트 케이스의 수이다.

최대 10개의 테스트 케이스가 표준 입력을 통하여 주어진다.

각 테스트 케이스에는 숫자판의 정보와 교환 횟수가 주어진다.

숫자판의 정보는 정수형 숫자로 주어지고 최대 자릿수는 6자리이며, 최대 교환 횟수는 10번이다.

[출력]

각 테스트 케이스마다, 첫 줄에는 “#C”를 출력해야 하는데 C는 케이스 번호이다.

같은 줄에 빈 칸을 하나 사이에 두고 교환 후 받을 수 있는 가장 큰 금액을 출력한다.

입력

3
123 1
2737 1
32888 2
. . .

input.txt

출력

#1 321
#2 7732
#3 88832
. . .

output.txt

문제 요약) 정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산

정답 코드

하 이게 D3이라니... 너무 어려웠던 문제입니다. 풀다가 벽을 느꼈습니다.

저는 일단 재귀로 완탐 했다가 역시 시간 초과가 나서, 조건 이것저것 추가해 15개 중에 10개까지 맞히고 도저히 모르겠어서 정답 봤습니다.

DFS+백트래킹 으로 푸는 문제라고 합니다. (...) 보면 또 알겠는데 풀 때 떠올리기가 쉽지 않습니다.

T = int(input())

for test_case in range(1, T + 1):
    # 입력
    numbers, max_change_num = map(int, input().split())
    numbers = list(str(numbers)) # 문자열 리스트
    visited = [] # (누적 교환 횟수, 현재 숫자)를 저장해서 중복을 줄이기 위한 배열
    answer = 0 # 정답

    # 현재까지 change_num번 바꾼 상태에서
    # 아직 더 바꿀 수 있으면, 가능한 모든 쌍을 만들어본다
    # 교환할 수 있는만큼 다 했으면 현재 숫자를 answer와 비교해서 최댓값 업데이트
    def dfs(change_num):
        global answer
        # 교환 다 함
        if change_num == max_change_num:
            # 현재 answer와 현재 숫자를 비교해서 더 큰 값으로 answer 업데이트
            answer = max(answer, int(''.join(numbers)))
            # 재귀 종료
            return
            
        # 가능한 모든 쌍을 만들어서 교환한다
        for first in range(len(numbers)-1):
            for second in range(first+1, len(numbers)):
                # first 위치의 값과 second 위치의 값을 swap
                numbers[first], numbers[second] = numbers[second], numbers[first]
                # 교환해서 만들어진 숫자를 now_numbers에 저장
                now_numbers = int(''.join(numbers))
                # (누적 교환 횟수, 만들어진 숫자) 쌍으로 과거에 연산한 적이 없다면
                if (change_num, now_numbers) not in visited:
                    # 중복 탐색을 막기 위해 해당 쌍을 visited에 저장
                    visited.append((change_num, now_numbers))
                    # 교환 횟수+1해서 재탐색
                    dfs(change_num+1)
                # 이후 새로운 탐색에 영향을 주지 않기 위해 swap 했던 값 원상복구
                numbers[second], numbers[first] = numbers[first], numbers[second]
		
    # 0번의 교환에서 시작
    dfs(0)
    # 출력
    print("#%d %d" %(test_case, answer))

제가 놓쳤던 부분은 아래와 같습니다.

1. (교환 횟수, 숫자) 형태로 visited에 저장해서 중복 탐색을 방지한다.
2. 재귀 끝나고 원상복구 해야 된다.

[1번 설명]

예를 들어 현재까지 1번 교환했고 숫자가 321 인데, 이전에 (1, 321)이 왔을 때에 구했던 값이 있다면 이것도 결국 같은 값을 반환할 것이기 때문에 또 탐색할 필요가 없습니다.

단, (2, 321)과 (1, 321)은 남은 교환 횟수가 다르기 때문에 반환하는 값이 달라집니다. 그래서 숫자만 visited에 저장하는 것이 아니라 누적 교환 횟수와 숫자 쌍을 튜플로 묶어서 visited에 저장해야 합니다.

[2번 설명]

재귀 함수가 공유된, 변경 가능한 리스트(numbers)를 사용하기 때문에 한번 숫자를 교환하고 나면 그 상태가 다음 재귀 호출에도 그대로 전달됩니다. first에 위치한 값과 second에 위치한 값을 교환하고 교환 횟수가 남았을 때는 그 교환된 숫자로 재귀를 쭉~ DFS로 파고 들어갑니다. 그래서 계속 교환된 숫자를 또 교환하고, 교환된 숫자를 교환하고 … (반복) 합니다.

그러나 주어진 교환 횟수만큼 다 교환하고 return 으로 재귀가 종료된 이후에는, 다시 새로운 first와 second 인덱스를 얻어서 ‘원래 numbers 숫자에서’ 새 두 쌍을 교환해야 합니다. 이를 위해 재귀 호출 이후에 numbers[second], numbers[first] = numbers[first], numbers[second] 이 코드를 두어 교환시킨 값을 다시 바꾸어 원상복구를 해주어야 원래 numbers 숫자에서 새로 탐색을 시작할 수 있습니다.

이상입니다.