11개의 포지션에 11명의 선수를 채웠을 때, 능력치의 합의 최댓값을 구하는 문제.
# 42분 소요. (한 번에 통과, PyPy3 제출 기준 시간 1위 달성했다!)
- 사용 알고리즘 : Backtracking, DFS 순열 구하기
- 무난하게 순열 구하는 dfs 재귀로 접근해 가지치기하여 가짓 수를 쳐냈다.
- 원래 dfs 순열로는 11개 자리에 11명을 각각 다른 자리에 배치하는 경우의 수가 39,916,800개가 나오는데, Backtracking으로 가지치기하면 경우의 수가 1824개로 확연히 준다.
- perm 함수에서 0~10 위치별로 돌리며 이미 다른 선수가 포지션을 차지했거나, 이 자리에서 해당 선수가 부적합하다면 continue해서 이로부터 파생될 수 있는 모든 가짓 수를 쳐낸다.(가지치기)
- 해당 포지션에 해당 선수가 올 수 있다면 방문 체크 해주고, 현재 점수에 낼 수 있는 점수를 더하며 다음 재귀(다음 player 탐색)로 보낸다.
- 11명의 선수가 모두 배치되면, 그 때의 score와 전역변수 max_score의 최댓값으로 갱신한다.
백트래킹에 대한 설명은 여기에 잘 정리해뒀다. 참고하길!
파이썬 코드는 다음과 같다.
from sys import stdin
input = stdin.readline
# 나의 풀이(176ms/123752kb)
def perm(player, score):
global max_score
if player == 11:
# print(order, score)
max_score = max(max_score, score) # 최대 점수 갱신
return
for i in range(11):
if visited[i] or not stats[player][i]: # 가지치기. 해당 포지션에서 적합하지 않으면 넘기기
continue
visited[i] = 1 # 방문 가능
order[player] = i
perm(player+1, score+stats[player][i])
order[player] = -1
visited[i] = 0
# main
T = int(input())
for _ in range(T):
stats = [list(map(int, input().split())) for _ in range(11)]
max_score = 0
order = [0] * 11 # 포지션별 선수 배치
visited = [0] * 11 # 방문 체크용
perm(0, 0)
print(max_score)
- 시간 : 176ms / 메모리 : 123752kb(PyPy3 제출)
- 고찰 : Gold 4라기엔 많이 쉬웠다. 체감상 실버 1정도..? 내 생각에 백준 N과 M(1) 문제만 수월하게 풀 수 있다면 아주 무난하게 맞았으리라 생각한다. Backtracking에 취약하니까 문제 더 많이 풀어보자!
'Problem Solving > boj' 카테고리의 다른 글
[BOJ] 1316. 그룹 단어 체커(Python) (0) | 2021.04.27 |
---|---|
[BOJ] 13335. 트럭(Python) / Simulation (0) | 2021.04.21 |
[BOJ] 1941. 소문난 칠공주(Python) / DFS, Backtracking (0) | 2021.04.13 |
[BOJ] 11725. 트리의 부모 찾기(Python) / BFS, DFS (0) | 2021.04.12 |
[BOJ] 1938. 통나무 옮기기(Python) / BFS (0) | 2021.04.11 |