예시 3: 세 수 곱의 합이 최대가 되는 배열 찾기

📖 학습 내용

문제 설명

양의 정수들을 서로 다른 순서로 배열했을 때, 연속한 세 수의 곱들을 모두 더한 값이 최대가 되는 배열의 최댓값을 구합니다.

입력 형식

쉼표로 구분된 양의 정수들을 입력합니다. 예) 1,2,3,4

출력 형식

가능한 모든 배열 중 규칙대로 계산한 값의 최댓값을 출력합니다.

원문 예시

공식 PDF 예시에서는 1,3,4,2 배열일 때 36이 최대입니다.

📥 테스트 입력값

1,2,3,4

🔎 실행 결과

💡 힌트 코치

학습용으로는 완전탐색이 가장 이해하기 쉽습니다. 모든 순열을 검사해 최댓값을 갱신하세요.

✅ 정답 공개

nums = [int(x) for x in input().strip().split(',')]
used = [False] * len(nums)
best = [-1]

def score(arr):
    total = 0
    for i in range(len(arr) - 2):
        total += arr[i] * arr[i + 1] * arr[i + 2]
    return total

def dfs(path):
    if len(path) == len(nums):
        best[0] = max(best[0], score(path))
        return
    for i in range(len(nums)):
        if not used[i]:
            used[i] = True
            path.append(nums[i])
            dfs(path)
            path.pop()
            used[i] = False

dfs([])
print(best[0])