CS 및 알고리즘 공부/알고리즘 문제 풀이

[알고리즘 문제 풀이🙄] 1244. 최대 상금

Gogumiing 2024. 9. 3. 11:55

📌 문제 요약

주어진 숫자판들 중 2개를 선택하여 정해진 횟수만큼 서로의 위치를 교환할 수 있다. (동일한 위치 교환이 중복되어도 됨)

교환이 끝난 후, 각 위치에 부여된 가중치에 의해 상금이 계산된다고 할 떄, 상금으로 받을 수 있는 가장 큰 금액을 계산하라. (왼쪽으로 갈수록 각 자리는 10의 배수만큼 가중치가 커진다. 가장 오른쪽 자리는 10^0만큼의 가중치를 가짐)

 

 

😖 내가 생각한 로직

  • 처음엔 순열 + 완전탐색으로 생각했는데, 횟수를 체크하는 로직을 추가하는 것이 어려웠다. 순열은 주어진 것들 중에 무작위로 뽑아서 배치하는 개념이므로 기존의 카드 배열과 비교하여 몇 번 이동하였는지를 계산해내야 했기 때문에 이를 해결하지 못했다.
  • 다음으로 N-queen과 같은 방식으로 접근해보고자 시도했는데, 중간에 또 머릿속에서 생각이 엉키면서 끝내 해결하지 못했다.

 

🤗 제출 후 pass한 코드

# N번 카드를 교환할 때까지 재귀적으로 수행
# idx: 카드를 교환한 횟수
def solve(idx):
    global max_result

    # 교환 횟수가 남아있지 않으면 종료
    if idx == N:        
        max_result = max(max_result, int(''.join(cards)))
        return

    # 모든 카드들에 대해 자신보다 뒤에 있는 카드들과 위치 변경
    for i in range(cards_num - 1):
        for j in range(i + 1, cards_num):
            cards[i], cards[j] = cards[j], cards[i]
            
            # 현재의 값 계산
            curr_num = ''.join(cards)
            
            # 교환했을 때, 과거에 비교되지 않은 값인 경우에만 계속 교환 진행
            if (idx, curr_num) not in visited:
                visited.add((idx, curr_num))
                solve(idx + 1)

            # 교환해봤으니 원래 모양대로 돌려놓기
            cards[i], cards[j] = cards[j], cards[i]


T = int(input())

for tc in range(1, T + 1):
    cards, N = input().split()
    cards = list(cards)             # 카드 리스트
    cards_num = len(cards)          # 카드 개수
    N = int(N)                      # 제한된 교환 횟수
    max_result = 0                  # 최대 상금

    # (횟수, 숫자) 저장
    visited = set()

    print(f'#{tc}', end = ' ')
    solve(0)
    print(max_result)

친구의 코드와 강사님의 코드를 참고하여 작성한 답안이다.

 

😎 앞으로의 개선 방향

 

 처음에 순열과 완전탐색에 꽂히고 나니 그 틀을 벗어나 생각하지 못했다. 그리고 다른 방식으로 접근을 시도했을 때에도 머릿속에 떠다니는 여러 로직들이 뒤엉켜서 하나의 로직으로 정리하지 못했다. 결국 코드로 구현을 완료하지 못했고, 나중에는 생각만 둥둥 떠다니고 코드는 한 줄도 작성하지 못하는 상태가 되었다.

 

 앞으로는 미리 로직을 완전히 세우기 전에는 코드를 작성하지 않도록 습관을 들여봐야겠다.