[BOJ] 백준_17127번_벚꽃이 정보섬에 피어난 이유_Python3

🌟 벚꽃이 정보섬에 피어난 이유

17127번: 벚꽃이 정보섬에 피어난 이유

조건

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	1362	898	788	69.427%

문제

정보섬에 벚꽃이 피어났다!

정보섬에 만발한 꽃송이들을 본 욱제는 한 가지 좋은 생각을 떠올렸다. 아래와 같은 네 개의 푯말을 준비해서 정보섬의 꽃밭에 세우는 것이다.

정보섬의 1층 꽃밭에는 총 N개의 벚나무가 일렬로 늘어서 있다. 각 벚나무에는 늘어선 순서대로 A1, A2, ..., AN개의 벚꽃이 피어나 있다. 욱제는 이 벚나무를 총 네 개의 그룹으로 나누어 각 그룹을 대표하도록 푯말을 세웠다.

이 그룹을 나눈 데에는 특별한 기준이 있다. 그룹 [i, j]의 벚꽃 개수들의 곱 Pi,j = Ai × Ai+1 × ... × Aj-1 × Aj (i ≤ j)가 네 개 있을 때, 네 개의 P의 합이 최대가 되도록 나누었다. 다시 말해, 그룹 내의 벚꽃 개수를 모두 곱하고, 그렇게 곱해진 값 네 개를 모두 더한 값이 최대가 되도록 나누었다. 욱제는 연속된 순서의 나무들만 하나의 그룹으로 묶고, 모든 나무들을 빠짐없이 정확히 하나의 그룹에 포함시켰다. 또한 하나의 그룹에는 반드시 하나 이상의 나무가 포함되었다.

힘든 하루를 마치고 집으로 돌아가던 당신은 정보섬 1층에 만발한 꽃송이와 푯말을 보았다. 그리고 갑자기 최대화 된 네 개의 P의 합이 얼마인지 궁금해졌다.

얼마일까?

입력

첫째 줄에 벚나무의 개수 N이 주어진다. (4 ≤ N ≤ 10)

둘째 줄에 N개의 나무에 피어난 벚꽃의 개수 Ai가 순서대로 주어진다. (1 ≤ Ai ≤ 5)

출력

얼마일까?

예제 입력 1

7
2 5 3 1 4 2 3

예제 출력 1

67

풀이 계획

list 값들을 네 덩이로 나누는 모든 경우를 생각해야 했다. 그러기 위해서 각각의 범위를 지정한 4중 for문으로 각 시작위치, 종료위치를 생각해서 그 만큼의 곱들을 multiple 메소드에서, 그 곱들의 합을 sumMultiple 메소드에서 리턴한다.

풀이

import sys

read = sys.stdin.readline

def multiple(a, b, arr):
    mul = 1
    for i in range(a, b):
        mul *= arr[i]
    return mul

def sumMultiple(i, j, k, l, arr):
    return multiple(i, j, arr) + multiple(j, k, arr) + multiple(k, l, arr) + multiple(l, len(arr), arr)

def solution():
    n = int(read())
    arr = tuple(map(int, read().split()))
    max_value = 0
    for i in range(0, 1):
        for j in range(i + 1, n - 2):
            for k in range(j + 1, n - 1):
                for l in range(k + 1, n):
                    if sumMultiple(i, j, k, l, arr) > max_value:
                        max_value = sumMultiple(i, j, k, l, arr)
    print(max_value)

solution()