흙금이네 블로그

아이디어 DFS과 백트래킹으로 남은 포지션에 선수들을 채워 나가며 능력치 합의 최댓값을 찾는다. 풀이 #1 (Python) 각각의 테스트 케이스에 대해 선수들의 능력치를 리스트 S에 입력 받는다. 메모리 절약과 DFS에서 빠른 접근을 위해 능력치가 0이 아닌 선수들만 인덱스와 능력치를 추가해 나간다. 포지션 할당 표시를 위해 0으로 채워진 리스트 visited를 생성하고 함수 dfs를 호출한다. 함수 dfs에서는 차례로 i 번째 선수를 적합한 포지션 중 남은 포지션에 배치하여 할당 표시 후, 현재 선수의 능력치 a를 능력치 합 total에 더하여 다음 선수로 함수를 재귀 호출한다. 배치가 끝나면 결과값 res와 능력치 합 total을 비교해 결과값을 능력치 합의 최댓값으로 갱신해 나간다. import s..