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

김멉덥·2023년 11월 3일
0

알고리즘 공부

목록 보기
111/171
post-thumbnail
post-custom-banner

문제

프로그래머스 PCCP 모의고사 #1


코드 구현

### 순열 풀이법
# 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]]))

풀이

  • 항상 순열이 익숙하고 DFS는 잘 생각이 안난다… 그리고 당연히 수열은 시간초과가 났다.
  • 능력치의 합을 최대화하는 문제이지만 각 분야에서 무조건 큰 수만 뽑으면 되는게 아님 → 한번 뽑히면 다른 곳에서는 못 뽑히기 때문
  • 따라서 최적의 해를 찾아가는 DFS로 풀 수 있는 문제
  • check 배열에서 학생 인원수만큼 0으로 넣어두고 → DFS 함수를 돌면서 그 학생이 뽑히면 1로 표시해두며 더해간다.
  • L을 늘려가며 뽑고 → 종목 개수만큼 뽑히면 현재 정답과 더해왔던 s 중에서 최댓값을 answer로 업데이트 해준다.
    • L : level (고를 수 있는 학생 수 중 몇 명째 선택한 것인지), s : 능력치의 합

profile
데굴데굴 뚝딱뚝딱 개발기록
post-custom-banner

0개의 댓글