[Python] 백준 3980 - 선발 명단

Overview

BOJ 3980번 선발 명단 Python 문제 풀이
분류: Backtracking (백트래킹)

---

문제 페이지

https://www.acmicpc.net/problem/3980

---

풀이 코드

from sys import stdin
from typing import List


def back_tracking(players: List[List[int]], occupied, cur: int, stats: int) -> int:
    if cur == 11:
        return stats

    res = 0
    for i in range(11):
        if not occupied[i] and players[cur][i] != 0:
            occupied[i] = True
            res = max(back_tracking(players, occupied, cur + 1, stats + players[cur][i]),
                      res)
            occupied[i] = False
    return res


def main():
    def input():
        return stdin.readline().rstrip()

    c = int(input())
    for _ in range(c):
        players = [list(map(int, input().split())) for _ in range(11)]
        occupied = [False] * 11
        print(back_tracking(players, occupied, 0, 0))


if __name__ == "__main__":
    main()

백트래킹 문제이다. dfs로 탐색하면서 각 11명의 선수들을 능력이 0보다 큰 모든 포지션에 넣어보며 가능한 모든 경우의 수를 구한다. 그리고 각각의 경우의 능력치 중에서 최대값을 구한다.