[SW Expert Academy, SWEA 1244] [S/W 문제해결 응용] 2일차 - 최대 상금 (python)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

---

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

728x90

---

내 생각

처음엔 앞에서 부터 오른쪽에 있는 원소 중 가장 큰 값으로 바꿔주도록 코드를 짰다.

근데 3번째 테스트 케이스의 경우

32888 -> 88823 이런 식으로 답이 나왔다.

 

그래서 여기를 참고하여 완전탐색으로 다시 풀었다.

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

for test_case in range(1, t + 1):
    # 숫자판의 정보 board, 교환 횟수 n
    board, n = input().split()
    n = int(n)
    # 중복을 제거한 경우의 수를 담아주기 위한 set
    now = set([board])
    nxt = set()
    
    # 교횐 횟수만큼 반복
    for _ in range(n):
        # now가 빌 때까지
        while now:
            s = now.pop()
            # 리스트로 변환
            s = list(s)
            # 가능한 모든 교환 경우의 수를 nxt에 담는다
            # set 자료구조의 특성상 중복은 알아서 걸러진다.
            for i in range(len(board) - 1):
                for j in range(i + 1, len(board)):
                    s[i], s[j] = s[j], s[i]
                    nxt.add(''.join(s))
                    # 원상복귀
                    s[i], s[j] = s[j], s[i]

        # 모든 경우의 수를 nxt에 담았으니
        # 다음 교환을 위해 now에 nxt를 nxt에 빈 set를 할당
        now, nxt = nxt, now

    answer = max(map(int, now))
    print("#{} {}".format(test_case, answer))