백준 2670 - 연속부분최대곱

https://www.acmicpc.net/problem/2670

2670번: 연속부분최대곱

 

위 문제는 DP를 이용해 푸는 전형적인 DP문제이다.

 

곱해지는 수로 인해 일시적으로 값이 작아져도 후에 뒤쪽에 1보다 큰 수가 위치할 경우, 커질 수 있기 때문에 뒤쪽까지 모두 탐색해보는 브루트포스 알고리즘을 사용했다. 

 

n = int(input())
a = []
for i in range(n):
    a.append(float(input()))

dp = [0 for i in range(n)]
tmp = 1
tmp2 = []
for i in range(len(a)):
    tmp = a[i]
    tmp2 = [tmp]
    for j in range(i+1, len(a)):
        tmp *= a[j]
        tmp2.append(tmp)
    dp[i] = max(tmp2)

result = max(dp)
print('%.3f'%max(dp))

그랬더니 시간초과가 나왔다.

 

질문 게시판을 뒤적거리다가 굉장히 좋은 풀이를 발견해서 풀었다

 

풀이코드 리뷰를 해보도록 하자.

 

풀이코드)

n = int(input())
a = []
for i in range(n):
    a.append(float(input()))

dp = [0 for i in range(n)]
dp[0] = a[0]
for i in range(1, len(a)):
    dp[i] = max(dp[i-1]*a[i], a[i])

print('%.3f'%max(dp))

1. 소수를 입력받아서 a 리스트에 담고 0으로 초기화한 n길이의 dp리스트를 생성한다.

2. 소수 리스트를 하나씩 탐색하는데 이 때, dp[0] = a[0]으로 초기화한다.

3. dp[i]는 i번째까지 고려했을 때의 최대값이다.

4. dp[i]에는 그 전까지인 i-1번째까지의 최대값 * i번째 소수 와 i번째 소수 사이에서 최대값을 저장한다.

==> 왜냐하면 dp[i-1]번째와 현재 i번째 소수를 곱함로써 연속적인 곱을 고려할 수 있고 그 값이 현재 i 번째 값보다 작을 경우, 계속해서 끌고 가 계산해볼 가치가 없기 때문에 둘 중 큰 값만 저장해서 사용해야하기 때문이다.

 

 

추가적으로 소수점에 대한 문법을 알아보자.

print('%.3f'%max(dp)) # 1.0을 넣으면 1.000으로 나옴
print(round(max(dp), 3)) # 1.0을 넣으면 1.0으로 나옴

 

위 아래 둘 다 소수점을 반복림하여 3번째 자릿수까지 나타내지만, 위는 소수점 뒤 자리를 3자리로 맞춰주고 아래는 소수점 뒤 자리가 3자리보다 작을 경우, 굳이 3자리로 맞추어주지 않는다는 차이점이 있다.