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)
친구의 코드와 강사님의 코드를 참고하여 작성한 답안이다.
😎 앞으로의 개선 방향
처음에 순열과 완전탐색에 꽂히고 나니 그 틀을 벗어나 생각하지 못했다. 그리고 다른 방식으로 접근을 시도했을 때에도 머릿속에 떠다니는 여러 로직들이 뒤엉켜서 하나의 로직으로 정리하지 못했다. 결국 코드로 구현을 완료하지 못했고, 나중에는 생각만 둥둥 떠다니고 코드는 한 줄도 작성하지 못하는 상태가 되었다.
앞으로는 미리 로직을 완전히 세우기 전에는 코드를 작성하지 않도록 습관을 들여봐야겠다.