프로그래머스
PCCP 모의고사 #1
- 2번 - 체육대회 (Python)
https://school.programmers.co.kr/learn/courses/15008/lessons/121684
### 순열 풀이법
# from itertools import permutations
#
# def solution(ability):
# answer = 0
#
# # 각 종목 대표의 해당 종목에 대한 능력치의 합을 최대화하기
# # 각 열에서 하나씩 뽑아서 더하기 & 한번 뽑은 행은 뽑을 수 없음 -> 최대값 만들기
#
# p_ability = list(permutations(ability, len(ability[0])))
#
# for i in range(len(p_ability)):
# p_sum = 0
# for j in range(len(p_ability[i])):
# p_sum += p_ability[i][j][j]
# answer = max(answer, p_sum)
#
# return answer
#
### DFS 풀이법
answer = 0
def DFS(L, s, ability, check):
global answer
n = len(ability) # 학생 수
m = len(ability[0]) # 종목 개수
if L == m:
answer = max(answer, s) # 능력치 합의 최댓값을 구함
else:
for i in range(n):
if check[i] == 0:
check[i] = 1
DFS(L + 1, s + ability[i][L], ability, check)
check[i] = 0
def solution(ability):
global answer
check = [0] * len(ability)
DFS(0, 0, ability, check)
# Level, sum, ability, check
# L : level (고를 수 있는 학생 수 중 몇 명째 선택한 것인지), s : 능력치의 합
return answer
if __name__ == '__main__':
print(solution([[40, 10, 10], [20, 5, 0], [30, 30, 30], [70, 0, 70], [100, 100, 100]]))
check
배열에서 학생 인원수만큼 0으로 넣어두고 → DFS 함수를 돌면서 그 학생이 뽑히면 1로 표시해두며 더해간다.L
을 늘려가며 뽑고 → 종목 개수만큼 뽑히면 현재 정답과 더해왔던 s
중에서 최댓값을 answer
로 업데이트 해준다.L
: level (고를 수 있는 학생 수 중 몇 명째 선택한 것인지), s
: 능력치의 합