코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
PCCP 모의고사 #1 - 체육대회
앞서 공부한 DFS(깊이 우선 탐색)을 사용해 체육대회 문제를 풀어보겠다.
문제 설명
당신이 다니는 학교는 매년 체육대회를 합니다. 체육대회는 여러 종목에 대해 각 반의 해당 종목 대표가 1명씩 나와 대결을 하며, 한 학생은 최대 한개의 종목 대표만 할 수 있습니다. 당신의 반에서도 한 종목당 1명의 대표를 뽑으려고 합니다. 학생들마다 각 종목에 대한 능력이 다르지만 이 능력은 수치화되어 있어 미리 알 수 있습니다. 당신의 반의 전략은 각 종목 대표의 해당 종목에 대한 능력치의 합을 최대화하는 것입니다.
다음은 당신의 반 학생이 5명이고, 종목의 개수가 3개이며, 각 종목에 대한 학생들의 능력치가 아래 표와 같을 때, 각 종목의 대표를 뽑는 예시입니다.
| 테니스 | 탁구 | 수영 | |
|---|---|---|---|
| 석환 | 40 | 10 | 10 |
| 영재 | 20 | 5 | 0 |
| 인용 | 30 | 30 | 30 |
| 정현 | 70 | 0 | 70 |
| 준모 | 100 | 100 | 100 |
테니스 대표로 준모, 탁구 대표로 인용, 수영 대표로 정현을 뽑는다면, 세 명의 각 종목에 대한 능력치의 합은 200(=100+30+70)이 됩니다.
하지만, 테니스 대표로 석환, 탁구 대표로 준모, 수영 대표로 정현을 뽑는다면 세 명의 각 종목에 대한 능력치 합은 210(=40+100+70)이 됩니다. 이 경우가 당신의 반의 각 종목 대표의 능력치 합이 최대가 되는 경우입니다.
당신의 반 학생들의 각 종목에 대한 능력치를 나타내는 2차원 정수 배열 ability가 주어졌을 때, 선발된 대표들의 해당 종목에 대한 능력치 합의 최대값을 return 하는 solution 함수를 완성하시오.
제한사항
- 1 ≤
ability의 행의 길이 = 학생 수 ≤ 10 - 1 ≤
ability의 열의 길이 = 종목 수 ≤ability의 행의 길이 - 0 ≤
ability[i][j]≤ 10,000ability[i][j]는i+1번 학생의j+1번 종목에 대한 능력치를 의미합니다.
입출력 예
| dungeons | result |
|---|---|
| [[40, 10, 10], [20, 5, 0], [30, 30, 30], [70, 0, 70], [100, 100, 100]] | 210 |
| [[20, 30], [30, 20], [20, 30]] | 60 |
입출력 예 설명
입출력 예 #1
- 문제 예시와 같습니다.
입출력 예 #2
- 1번 학생이 2번 종목을, 2번 학생이 1번 종목의 대표로 참가하는 경우에 대표들의 해당 종목에 대한 능력치의 합이 최대가 되며, 이는 60입니다.
코드
# 여러 종목이 있는데 각 반의 해당 종목 대표 1명씩 나옴
# 대신 1명당 1개의 종목 대표만 할 수 있다.
# 이 능력의 최대합을 구해라
answer = 0
def DFS(L, stats, ability, ch):
global answer
# 인원 수
n = len(ability)
# 종목 수
m = len(ability[0])
# 하나의 능력치 합이 완성됐냐 ?
if L == m:
# 그럼 기존까지 높았던 능력치 합 answer과 현재의 능력치 합 중 큰 값을 저장
answer = max(answer, stats)
else:
# 완성 안 됐다면 처음사람부터 종목 대표 추가해봄
# ex) 테니스 찾는중
for i in range(n):
# 지금 학생이 종목에 나가있지 않은 경우
# ex) 석환이 먼저
if ch[i] == 0:
# 나갔다고 표시
# ex) 석환 테니스 대표로 우선 선정
ch[i] = 1
#
# ex) 그다음 탁구 종목 대표 구하기
DFS(L+1, stats+ability[i][L], ability, ch)
ch[i] = 0
def solution(ability):
global answer
answer = 0
# 종목 나갔는지 확인용
ch = [0] * len(ability)
DFS(0, 0, ability, ch)
return answer
print(solution([[40, 10, 10], [20, 5, 0], [30, 30, 30], [70, 0, 70], [100, 100, 100]]))풀이
- 능력의 최대합
answer를 DFS를 호출했을 때 수정할 수 있게 전역 변수로 선언한다. - 학생당 한 종목만 참여 가능하므로 참여했다고 표시할 리스트 ch를 생성
- 그 후 DFS에 L(현재 종목), 현재 능력 최대합(stats), 능력치(ability), 참여 표시(ch)를 넣어 호출
- 호출되면 먼저
마지막 종목(L)까지 구했냐고 물어보고 구했다면, 기존까지 높았던 능력치 합answer과 현재의 능력치 합stats중 큰 값을 저장 - 아직 모든 종목을 더하지 못했다면, 참여하지 않은 학생들을 찾아보며 찾았다면
ch에 참여했다고 표시를 하고, 해당 종목의 그 학생의 능력치를stats에 더한 후 다음 종목을 찾아본다. - 그렇게 모든 경우의 수를 다 찾아 가장 높은 능력치 합
answer를 찾았다면return한다.
끄적끄적