[프로그래머스] PCCP 모의고사 1회 2번 체육대회

사용 언어 - Python3

문제 - 체육대회

https://school.programmers.co.kr/learn/courses/15008/lessons/121684

프로그래머스

 

 

정답

구현

가능한 모든 조합(순열) 구하기

 

(내 풀이)

permutations 가능한 사람 인덱스의 모든 조합

from itertools import *

from itertools import permutations (순열)

 

1. 사람인덱스 설정하기

5명일 경우, p_index= [0,1,2,3,4]

 

2. 가능한 사람 인덱스의 모든 조합(순열) 구하기

5명의 사람이 3개의 종목일 경우 총 5*4*3의 경우가 있다.

(0,1,2),(0,1,3),(0,1,4)....

list(permutaions([0,1,2,3,4], 3)

result = list(permutations(p_index,len(ability[0])))

 

3. 모든 조합의 능력치를 더하면서 최대값을 구하기

ability[사람번호][종목번호]

 ability[r[j][j]

사람번호 = r[j] = 모든 가능한 경우

종목번호 = j

 

from itertools import *

def solution(ability):
    # 한 종목당 1명의 대표
    # 해당 종목에 대한 능력치의 합 최대화
    answer = 0
    p_index = [i for i in range(0,len(ability))] # 사람 인덱스
    result = list(permutations(p_index,len(ability[0]))) # 가능한 사람 인덱스의 모든 조합(순열)
    
    for r in result: 
        sum = 0 # 능력치 합
        for j in range(len(ability[0])): # 종목수
            sum += ability[r[j]][j]
        answer = max(answer,sum)
        
    return answer

 

(좋은 풀이)

DFS를 사용하는 방법

DFS(종목수, 능력치합, ability, 종목나갔는지 확인)

 

0. DFS(0,0,ability,ch)에서 시작한다.

ch = [0] * len(ability)

해당 사람이 종목에 나갔는지 확인할 ch 리스트를 생성한다.

 

1. 한 사람씩 방문하면서 그 사람이 종목에 나가있지 않은 경우,

그 종목의 대표로 선정해주고, 나갔다고 체크해준다.

if ch[i] == 0: # 사람(i)가 종목에 나가지 않은 경우

  ch[i] = 1 # 출전 O  

 

2. 그 다음 종목에 나갈 학생을 구해준다.

DFS(L+1, stats + ability[i][L], ability, ch)

현재까지의 능력치합 stats 에 해당 학생의 능력치를 더한다.

 

3. L == 모든 종목수

모든 종목에 모든 사람이 나간 경우, 현재까지의 능력치와 answer중 큰 값을 저장한다.

 

def dfs(L, result, ability, ch):
    global answer
    n = len(ability) # 학생수
    m = len(ability[0]) # 종목수
    
    if L == m:
        answer = max(answer,result) # 능력치 합의 최대값
    else:
        for i in range(n): # 모든 학생 확인
            if ch[i] == 0: # 해당 학생이 종목에 나가지 않은 경우
                ch[i] = 1 # 종목 출전
                dfs(L+1,result+ability[i][L], ability, ch)
                ch[i] = 0

def solution(ability):
    global answer
    answer = 0
    ch = [0] * len(ability) # 해당 학생이 종목에 나갔는지 확인할 list
    dfs(0,0,ability,ch) # 초기값 학생 0명, 능력치 합 0
    
    return answer

 

 

 

 

레퍼런스

 

https://velog.io/@hamsangjin/PCCP-PCCP-%EB%AA%A8%EC%9D%98%EA%B3%A0%EC%82%AC-1-%EC%B2%B4%EC%9C%A1%EB%8C%80%ED%9A%8C

[프로그래머스] PCCP 모의고사 #1 - 체육대회 | 파이썬