[백준/Python] (S2) 1912- 연속합

연속합 성공

 

 

1912번: 연속합

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

128 MB

142794

54278

38623

36.610%

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

33

예제 입력 2 복사

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

예제 출력 2 복사

14

예제 입력 3 복사

5
-1 -2 -3 -4 -5

예제 출력 3 복사

-1

---

dp에서는 연속 합을 구하는 문제가 꽤 많이 나와서 열심히 연습중이다.

 

이번 문제는 처음에 다음과 같은 알고리즘을 생각해냈다.

 

이런식으로 계산하면서 배열에 각 원소가 리스트인 형태로 저장되었고, 이 리스트에 대한 공식은 다음과 같이 나왔다.

dp[i-1][j] + dp[i-1][j+1] - dp[i-2][j+1]

세운 공식을 가지고 반복문을 돌렸더니 답이 잘 나왔다.

#1912 연속합
import copy

n = int(input())

dp = []
temp = [] #다음 배열을 저장할 변수
temp = list(map(int,input().split())) #입력값 받기

dp.append(copy.deepcopy(temp)) #첫번째 리스트를 0번에 저장
temp.clear()

#1번째 리스트를 생성
for i in range(n-1):
    temp.append(dp[0][i] + dp[0][i+1])
    
dp.append(copy.deepcopy(temp)) #두번째 리스트를 1번에 저장
temp.clear()

for i in range(2, n):
    for j in range(len(dp[i-1])-1):
        temp.append(dp[i-1][j] + dp[i-1][j+1] - dp[i-2][j+1])
        
    dp.append(copy.deepcopy(temp))
    temp.clear()
    
#최댓값 찾기
print(max(map(max,dp))

하지만 위의 공식으로는 시간초과가 나왔고, 머리를 굴리다 도저히 안돼서 다른 블로그의 자료를 참고하였다.

 

#1912 연속합
n = int(input())
arr = list(map(int,input().split()))
dp = [0] * n

dp[0] = arr[0]

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

print(max(dp))

 

즉, dp를 길이만큼 초기화하고, i번째 원소는 이전 원소 + 입력된 원소 와 입력된 원소 두개를 비교해 더 큰것을 저장하는 형식이다.

이렇게 하면 (예제 1 기준으로) dp가 10, 6, 9, 10, 15, 21, -14, 12, 33, 33으로 저장된다.

 

위에서 12가 나온 부분을 잘 보면 arr에 받은 원소 중 12의 인덱스가 동일한것을 알 수 있다.

즉, 앞에서 더하다가 더 큰것을 가져오기 때문에 뒤에 올 수보다 작아진다면 버리고 새로 더할 지점을 정하는것과 같다.

(이해가 좀 어려웠는데 읽어보는 사람들 모두 위의 코드를 종이에 써서 돌려보면 충분히 이해가 가능하다.)

 

아직 dp에 대한 자신감도 없고, 특히 점화식을 정확히 세우는것이 조금 어렵기 때문에 더 풀어봐야 할것같다.