[SWEA] 1206. [S/W 문제해결 기본] 2일차 - 최대 상금 (DFS)

✍️ 문제 요약

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE

SW Expert Academy

 

숫자판과 교환 횟수가 주어진다. 주어진 숫자판들 중 두 수를 선택해서 정해진 횟수만큼 교환해야 할 때, 가장 큰 수를 만들어라.

 

 

💪 무식하게 풀기

구현이 어렵다기 보다는 생각해야 하는 조건이 까다로운 문제였다. 🥲

 

1. for문으로 상금(`price`)의 각 자리를 순회하면서, 나(`price[i]`) 이후에 나보다 큰 max가 있으면 나와 교환할 것이다.

    1-1. 이때, 값이 같은 max가 두 개 이상 있으면서 && 내 뒤에 나보다 작은 값이 있으면 -> 나는 맨 오른쪽 max가 아닌, 맨 오른쪽 max에서 한 칸 앞의 max와 교환해야 한다. ⭐️

    1-2. 만약 max가 한 개이거나 || 두 개 이상이라도 내 뒤에 나보다 작은 값이 없다면 -> 나와 맨 오른쪽 max를 교환한다.

 

2. for문을 다 돌았는데 교환 횟수(`N`)가 남았다면

    2-1. 상금(`price`)에 같은 수가 두 개 이상 있다면 -> 그대로 종료한다. (같은 수끼리 계속 교환해서 교환 횟수를 소모하면 되기 때문)

    2-2. 상금이 모두 다른 수로 구성되어 있다면

        2-2-1. 교환 횟수(`N`)가 짝수개 남았다면 -> 그대로 종료한다. (아무거나 두 개 교환하고 다시 원상복귀하면 되기 때문)

        2-2-2. 교환 횟수(`N`)가 홀수개 남았다면 -> 제일 오른쪽 두 자리를 한 번만 교환한다. (짝수번은 원상복귀할 수 있다고 했다. 따라서, 홀수번은 짝수번 + 1 이므로 한 번만 교환하면 된다. 교환 횟수를 모두 소모해야 하기 때문에 무조건 한 번은 교환해야 한다. 따라서, 수가 최소한으로 작아지도록 맨 오른쪽 두 자리를 교환하자.)

import sys
sys.stdin = open("input.txt", "r")
sys.stdout = open("output.txt", "w")

def find_all_max_index(start_idx):
    mx = -1e9
    max_idx = []
    for i in range(start_idx, len(price)):
        if price[i] > mx:
            mx = price[i] # 최댓값 갱신
            max_idx = [i]
        elif price[i] == mx:
            max_idx.append(i)
    return max_idx # 모든 최댓값 인덱스

# lst에 공통 원소 2개 이상 존재하는지 확인
def is_exist_duplicated_value(lst):
    visited = [0] * 10
    for x in lst:
        visited[x] += 1
        if visited[x] > 1: return True
    return False

# 나 이후에 나보다 작은 원소 있는지 확인
def is_exist_smaller_than_me(start_idx, target):
    for i in range(start_idx, len(price)):
        if price[i] < target: return True
    return False

if __name__ == '__main__':
    T = int(input())
    for test_case in range(1, T+1):

        price, N = map(int, input().split())
        price = list(map(int, str(price)))

        for i in range(len(price)):
            # 나 이후 원소들 중 max가 나보다 크면 나와 변경할건데
            if len(find_all_max_index(i+1)) > 0 and price[i] < price[find_all_max_index(i+1)[0]]:
                # 1) 같은 max가 두 개 이상 있으면서, 내 뒤에 나보다 작은 값 있으면 -> 나는 마지막 한 칸 왼쪽과 교환 (마지막 말고)
                if len(find_all_max_index(i+1)) >= 2 and is_exist_smaller_than_me(i+1, price[i]):
                    price[i], price[find_all_max_index(i+1)[-2]] = price[find_all_max_index(i+1)[-2]], price[i]
                else: # 2) 아니라면 나와 마지막 교환
                    price[i], price[find_all_max_index(i + 1)[-1]] = price[find_all_max_index(i + 1)[-1]], price[i]
                N -= 1
                if N == 0: break

        # N(교환 횟수)이 남았다면
        if N > 0 and not is_exist_duplicated_value(price) and N % 2 == 1:
            # 어쩔 수 없이 제일 오른쪽 두 자리 변경
            price[-1], price[-2] = price[-2], price[-1]

        print('#{}'.format(test_case), end=' ')
        print(*price, sep='')

 

✨ 우아하게 풀기 (DFS)

DFS를 이용해서 완전탐색으로 풀 수도 있다.

모든 경우의 수를 다 완전탐색하게 되면 15^10까지의 경우의 수가 나오기 때문에 ⭐️ 가지치기가 중요하다!

 

1. 우선 상금(`price`)을 입력 받은 뒤, 상금의 자리수만큼 `index` 리스트를 생성해놓자. (DFS 할 때 `combinations()` 메서드를 이용하기 위해서이다.)

 

2. 이제 DFS를 통해 모든 경우의 수를 탐색한다.

 

교환 횟수가 `N`이기 때문에, Level(`L`)이 N이 될 때 최댓값(`mx`)을 갱신한다. (예를 들어 `price` = [1,2,3] 이라면 `int(''.join(map(str, price)))`는 123(백이십삼)이 된다.)

 

그리고 아까 생성해놓은 `index` 리스트 중 순서 없이(combination) 두 개를 뽑는다. (이때 뽑은 수는 price의 '인덱스'이다.)

 

그리고 러프하게는 뽑은 두 수를 교환한뒤 다음 DFS(`DFS(L+1)`)를 호출하고, 이때 교환한 두 수를 다시 원래대로 돌려놓아야하기 때문에 DFS 호출 이후에 한번 더 교환해놓으면 된다. (하지만 다음 DFS를 호출하기 전에 '가지치기'를 해야 시간초과가 안난다!)

 

가지치기를 어떤 기준으로 할까❓ 
숫자와 그 때의 레벨을 `visited` 배열에 담아놓으면 된다❗️ (이때 말하는 레벨은 '몇 번째 교환인지'를 의미한다.)

예를 들어, [3,2,8,8,8]이라는 숫자판이 주어졌을 때,
첫 번째 교환에서 2번인덱스 <-> 3번 인덱스를 교환했다고 가정하자. 그럼 `visited`에 `(1, 32888)`을 추가하는 것이다.
두 번째 교환에서 또 2번 인덱스 <-> 3번 인덱스를 교환했다면, `visited`에 `(2, 32888)`을 추가한다.

중요한 것은, 수가 같더라도 그게 몇 번째 교환(=레벨)인지에 따라 의미가 다르니, `visited`에 수와 레벨을 꼭 함께 저장해야 한다는 것이다.

그리고 DFS를 호출하기 전에 해당 (레벨, 수)가 `visited`에 있는지 확인한다. `visited`에 이미 존재한다면 더 이상 갈 필요가 없는 길인 것이다. (이전에 이미 같은걸 했었기 때문!) 

 

from itertools import combinations

def DFS(L):
    global mx
    if L == N:
        mx = max(mx, int(''.join(map(str, price))))
        return
    for a, b in combinations(index, 2):
        price[a], price[b] = price[b], price[a]
        num = int(''.join(map(str, price))) # 가지치기를 위해
        if (L, num) not in visited:
            DFS(L+1)
            visited.append((L, num)) # 다 갔다가 올라오면서 체크
        price[a], price[b] = price[b], price[a] # 원상복구 (백트래킹)

T = int(input())
for test_case in range(1, T+1):
    price, N = map(int, input().split())
    price = list(map(int, str(price)))
    index = [x for x in range(len(price))]
    visited = []

    mx = -1e9
    DFS(0)
    print('#{} {}'.format(test_case, mx))

 

🔗 참고

백트래킹 #12 최대 상금 (SWEA)