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

문제 링크

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

문제

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

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

예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 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
. . .

출력

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

---

정답 및 풀이

def dfs(n,cnt):
    if (n,cnt) in visited:
        return

    visited.add((n,cnt))

    if cnt == change:
        result.append(int(n))
        return

    list_num = list(n)
    for i in range(len(n)):
        for j in range(i+1,len(n)):
            list_num[i],list_num[j] = list_num[j],list_num[i]
            dfs("".join(list_num),cnt+1)
            list_num[i],list_num[j] = list_num[j],list_num[i]

t = int(input())

for tc in range(t):
    num,change = input().split()

    change = int(change)

    visited=set()
    re02
    sult=[]

    dfs(num,0)

    print(f'#{tc+1} {max(result)}')

• dfs 함수

1. def dfs(n, cnt):
   • 현재 숫자 상태 n과 지금까지 교환한 횟수 cnt로 DFS 탐색을 수행하는 함수다.
2. if (n, cnt) in visited:
   • 동일한 숫자 상태가 동일한 교환 횟수에 다시 등장했다면 중복이므로 탐색을 중단한다.
3. visited.add((n, cnt))
   • 현재 상태 (n, cnt)를 방문 기록에 저장한다.
   • 다음에 같은 상태가 나오면 다시 계산하지 않기 위함이다.
4. if cnt == change:
   • 교환 횟수를 모두 사용한 경우 더 이상 교환할 수 없다.
5. result.append(int(n))
   • 현재 숫자 n을 정수로 저장해 결과 리스트에 추가한다.
6. return
   • 이 DFS 경로를 종료한다.
7. list_num = list(n)
   • 문자열은 변경할 수 없으므로, 자리 교환을 가능하게 하려고 리스트로 변환한다.
8. for i in range(len(n)):
   • 왼쪽 자리(i)를 기준으로 가능한 모든 교환을 시도하는 첫 번째 반복문이다.
9. for j in range(i+1, len(n)):
   • 오른쪽 자리(j)와의 교환을 시도하는 반복문이다.
   • i보다 뒤에 있는 자리와만 교환하여 중복 swap을 방지한다.
10. list_num[i], list_num[j] = list_num[j], list_num[i]
    • 실제로 두 숫자 자리를 교환한다.
11. dfs("".join(list_num), cnt + 1)
    • 교환된 숫자를 문자열로 다시 만들어
    • 교환 횟수를 +1한 후 다음 DFS 탐색을 진행한다.
12. list_num[i], list_num[j] = list_num[j], list_num[i]
    • 백트래킹 단계로,
    • 원래 숫자로 되돌려 다음 교환을 시도할 준비를 한다.

• main

1. t = int(input())
   • 테스트 케이스 개수를 입력받는다.
2. for tc in range(t):
   • 테스트 케이스 수만큼 반복한다.
3. num, change = input().split()
   • 숫자 문자열과 교환 횟수를 입력받는다.
   • 예: "1234", "2" 와 같은 입력.
4. change = int(change)
   • 교환 횟수를 정수형으로 변환한다.
5. visited = set()
   • 중복 상태를 막기 위한 방문 저장소를 초기화한다.
   • 테스트 케이스마다 새로 초기화된다.
6. result = []
   • 모든 가능한 교환 결과 숫자를 저장할 리스트다.
7. dfs(num, 0)
   • 초기 숫자 num과 교환 횟수 0에서 DFS 탐색을 시작한다.
8. print(f'#{tc+1} {max(result)}')
   • DFS가 만든 가능한 모든 숫자 중 가장 큰 숫자를 출력한다.
   • SWEA 형식에 맞춰 #1, #2 형태로 결과를 출력한다.

---

새롭게 배운 내용 및 느낀점

• 백트래킹(backtracking)
  • 모든 경우의 수를 탐색하되, 잘못된 선택을 했을 때 이전 상태로 돌아가 다른 선택을 시도하는 알고리즘 기법