SWEA 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 (Python, 완전탐색)

SWEA 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 문제 바로가기

문제 접근

이 문제는 처음 접근할 때 그리디로 생각했다..
하지만 그리디로 접근할 경우에 많은 조건을 추가적으로 붙여줘야 해서 아무래도 완전탐색으로 풀어야겠다고 생각했다.
완전탐색으로 풀기 전에 생각해야 할 것은 시간초과가 나느냐?이다.
최대 6자리 최대 10번의 교환횟수가 나올 수 있기 때문에 6C2^10로 15의 10승의 경우의 수를 가진다.
이렇게 될 경우 너무 많은 경우의 수의 등장으로 시간초과가 날 수 있다.
따라서 완전탐색으로 풀어나가고 가지치기를 통해서 불필요한 경우를 탐색하는 것을 방지해야 한다!

문제 풀이

DFS로 완전탐색

우선 종료 조건은 n이 교환횟수 N과 같아질 때 함수를 종료해야 한다.
우리는 그러한 값들 중 가장 큰 값을 구하고 싶기 떄문에 answer에 더 큰 값을 저장하고 함수를 종료한다.
모든 경우의 수에 대해서 진행했기에 가능한 경우중 가장 큰 값이 저장될 것이다.

def dfs(n):
    global answer
    if n==N:
        answer = max(answer, int("".join(map(str, lst))))
        return        
    for i in range(L-1):
        for j in range(i+1, L):
            lst[i], lst[j] = lst[j], lst[i]

     		dfs(n+1)
            
            lst[j], lst[i] = lst[i], lst[j]

가지치기

위에서는 dfs를 진행하는데에 조건이 없었다. 가지치기를 하려면 이 부분에 조건을 붙여줘야한다.
앞서 이미 갔던 길이라면 그 길을 가지 않도록 하는게 이 문제의 핵심이다.
v라는 리스트에 교환 횟수와 현재 숫자를 넣는다. 이 리스트에 들어가 있는 값들은 이미 지나온 길이다. 따라서 다음번에 dfs를 진행할 때 지나온 길인가?를 확인하고 만약 지나온 길이라면 다시 가지 않고, 처음 가는 길이면 dfs(n+1)을 통해 더 나아간다.

   chk = int("".join(map(str, lst)))
            if (n, chk) not in v:
                dfs(n+1)
                v.append((n,chk))

제출 코드

# 완전탐색에서 가지치기
# 15의 10승임
def dfs(n):
    global answer
    if n==N:
        answer = max(answer, int("".join(map(str, lst))))
        return        
    for i in range(L-1):
        for j in range(i+1, L):
            lst[i], lst[j] = lst[j], lst[i]

            chk = int("".join(map(str, lst)))
            if (n, chk) not in v:
                dfs(n+1)
                v.append((n,chk))

            lst[j], lst[i] = lst[i], lst[j]


T = int(input())

for test_case in range(1, T + 1):
    st, t = map(str, input().split())
    N = int(t)
    lst, v = [], []
    L = len(st)
    answer = 0
    for i in st:
        lst.append(i)
    dfs(0)
    print(f'#{test_case} {answer}')