[Python, 파이썬] SWEA 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

정해진 횟수만큼 숫자판을 교환했을 때, 가장 큰 상금 값을 구하는 문제.

  

 

def DFS(count):
    global result # 현재까지 발견된 최대 숫자

    if(count == 0): # 교환 횟수 달성 시 max 비교
        _max = int(''.join(keypad)) 
        result = max(_max, result) # 값 비교
        return

    for now in range(len(keypad)-1): # 현재 번호판
        for max_idx in range(now+1, len(keypad)): # 다음 번호판 돌면서 확인

            keypad[now], keypad[max_idx] = keypad[max_idx], keypad[now] # 번호판 교환

            cur = ''.join(keypad)
            if not (cur, count) in visited:
                visited.append((cur, count))
                DFS(count-1) # 교환횟수 차감해서 다시 호출
                
            keypad[now], keypad[max_idx] = keypad[max_idx], keypad[now] # 백트래킹

        
T = int(input()) # 테스트 케이스의 수 T

for test_case in range(1, T+1):
    keypad, cnt = input().split() # 숫자판의 정보, 교환 횟수
    keypad = list(keypad) # list()로 문자열 쪼개기

    result = 0
    visited=[]
    DFS(int(cnt))   
            

    print("#%d %s" %(test_case, result))

 

 

[문제풀이]

---

 

솔직히 이 문제는 못풀어서 포인트로 다른 분 코드를 참고했다.

 

for문을 사용한 Greedy 방식으로는 풀기가 어려운 문제다.

이 방식은 우선 가장 큰 숫자를 땡겨와야 하는데, 이로서 끝나는 문제가 아니다.

32881 -> 82831 (SWAP 1회시 최적O) -> 88231 (SWAP 2회시 최적X)
32881 -> 82381 (SWAP 1회시 최적X) -> 88321 (SWAP 2회시 최적O)

 

예를 들면 위처럼 32881이란 숫자일 경우 가장 큰 숫자 8을 앞으로 땡겨오는 첫 swap 시는 최대 상금이지만 그 다음 swap 시에는 아니게 된다. 그래서 무식하게 조건을 왕창 추가해 가며 풀어야 하는데 그래도 테스트 케이스 모두 통과하기가 무척 어렵다.

 

그러니 DFS+백트래킹을 활용한 완전탐색이 필요하다.

처음부터 어떤 숫자들끼리 바꿀지 선택하지 말고, 모든 숫자들을 다 바꿔가며 풀어야 하는데 완전 탐색으로 모든 교환을 시도할 시 시간 초과가 발생한다.

if not (cur, count) in visited:
    visited.append((cur, count))

 

그래서 메모이제이션을 활용,

visited란 배열에 이미 방문했던 숫자와 교환 횟수를 기록해두고 같은 수가 나올 시 더 이상 탐색을 진행하지 않았다.