🚩 코딩테스트/알고리즘
[프로그래머스] [PCCP 모의고사 #1] 체육대회
딩딩크롱
2023. 2. 18. 18:16
728x90
문제
https://school.programmers.co.kr/learn/courses/15008/lessons/121684
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
DFS(깊이 우선 탐색)를 사용했습니다.
stack
에 각 종목 순으로 저장합니다.
예를 들어 stack[0]
은 테니스, stack[1]
은 탁구, stack[2]
는 수영이 저장됩니다.
모든 조합을 구하여 최대 합을 구합니다.
코드
파이썬
def solution(ability):
n_students = len(ability)
n_items = len(ability[0])
check = [False] * n_students
stack = []
answer = 0
def get_sum(n):
_sum = 0
for i in range(n):
_sum += ability[stack[i]][i]
return _sum
def DFS(L):
nonlocal answer
if L == n_items:
answer = max(answer, get_sum(n_items))
else:
for i in range(n_students):
if not check[i]:
check[i] = True
stack.append(i)
DFS(L+1)
stack.pop()
check[i] = False
DFS(0)
return answer
728x90