BOJ 2670 - 연속부분최대곱

문제는 그다지 어려워 보이지 않는다.

연속되는 부분의 최대 곱의 값을 얼마인가.

그냥 n=0부터 n-1까지 순회하면서 구한 곱의 최댓값을 구하면 될 것 같다.

# BOJ 2670

def solve(n, ar):
    max_multi = 0
    for i in range(n):
        m = ar[i]
        for j in range(i + 1, n):
            m = m * ar[j]
            if max_multi < m:
                max_multi = m

    return round(max_multi, 4)


def test_solve():
    n = 8
    ar = [1.1, 0.7, 1.3, 0.9, 1.4, 0.8, 0.7, 1.4]
    assert solve(n, ar) == 1.638


if __name__ == "__main__":
    n = int(input())
    ar = [float(input()) for _ in range(n)]
    print(solve(n, ar))

물론 n이 10,000이니까 n^2의 시간 복잡도를 가질 테고

그러면 100,000,000으로 시간 복잡도가 꽤 커서 시간 초과가 날 것 같았다.

 

그런데 왠 걸.

WA가 나온다.

아.. 소수점 자리를 구하다가 오차가 생기는 것 같은데.

그럼 이제 어떻게 해야 할까?

 

고민 고민을 해보다가 구글링을 해봤다.

좀 더 간단한 설루션이 있었다. ㅠㅠ

O(n)의 시간 복잡도를 갖도록 계산이 가능한데,

핵심은 0 index부터 시작해서 그다음 index를 곱해서 곱한 값이 크면 치환한 후,
해당 배열에서 가장 큰 값을 리턴하는 식으로 구현하면 된다.

 

아래에 수정된 소스를 첨부한다.

# BOJ 2670
import sys


def solve(n, ar):
    for i in range(1, n):
        m = ar[i - 1] * ar[i]
        ar[i] = max(m, ar[i])

    return max(ar)


def test_solve():
    n = 8
    ar = [1.1, 0.7, 1.3, 0.9, 1.4, 0.8, 0.7, 1.4]
    assert "{:.3f}".format(solve(n, ar)) == "1.638"


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    ar = []
    for i in range(n):
        ar.append(float(sys.stdin.readline()))
    print("{:.3f}".format(solve(n, ar)))

스스로 구현한 부분은 오류가 있었지만

그래도 간단한 hint를 얻어 수정해서 풀어서 다행이다.

 

다음에도 비슷한 유형이 나오면 잊지 말고 활용할 수 있으면 좋겠다.