BOJ) 연속 합 - 파이썬

 

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

 

 

해당 문제의 알고리즘 분류는 DP가 된다. 

우선 가장 먼저 생각해 보아야할 것이 브루트 포스 알고리즘이다. n의 수 만큼 반복하며 각각의 모든 연속된 합 중 최대값을 구하는 방법이다.

 

하지만 해당 방법으로는 해당 문제의 최대 입력 값을 기준으로 100,000^2 시간 복잡도를 가지며 당연하게 시간초과가 나오고 만다.

 

그럼 가장 먼저 생각나는 것이 DP이다.

DP중 캐싱을 통한 방법으로 풀어보았다.

n = int(input())

arr = list(map(int, input().split()))
for i in range(1, n):
    arr[i] = max(arr[i], arr[i] + arr[i-1])

print(arr)

 

우선 정답 코드이다.

 

해당 문제는 n개의 배열 값들 중, arr[x]와 arr[x + y]값이 가장 크다고 가정할 때, 즉 다음 값이 최대값이 된다.

2 1 -4 3 4 -4 6 5 -5 1

 

그럼 x번째부터 시작하고 y번째까지 더해야 최대값이 나오는 것일까.

 

사실 이 문제는 딱 한가지 규칙만 지키면 무난하게 풀 수 있는 문제이다.

1. 배열의 각 정수를 반복문으로 순회하며 0번부터 x번째까지의 더한 값을 x번째에 저장한다.
2. 단, x번째의 값보다 x-1번째의 값이 더 작을 경우, x번째 값을 x번째에 저장한다.

이러한 방식으로 적절한 시작위치를 구할 수 있다.

 

예시로 한 번 보자.

다음 테스트 케이스가 존재한다.

 

10
10 -4 3 1 5 6 -35 12 21 -1

 

우선 인덱스 1에 들어갈 값을 구해야한다.

값을 구하는데있어 조건은 다음과 같다.

 

arr[1] = max(arr[1], arr[1] + arr[1-1])

#위 테스트 케이스대로라면 

arr[1] = max(-4, -4 + 10)

즉, arr[1] = 6이된다.

 

 

 

 

---

내가 맨 처음 제출했던 코드이다.

 

n = int(input())

arr = list(map(int, input().split()))
dp = [arr[0]]

for i in range(1, n):
    dp.append(max(arr[i], arr[i] + arr[i-1]))
print(max(dp))

 

내가 틀렸던 점은, arr[i] + dp[i-1]가 아닌,

arr[i] + arr[i-1]

로 작성했던 점이다.

만약 위와같은 코드로 작성했을 경우의 정답은 다음과 같다.

 

n = int(input())

arr = list(map(int, input().split()))
dp = [arr[0]]

for i in range(1, n):
    dp.append(max(arr[i], arr[i] + dp[i-1]))
print(max(dp))