[백준/Python] (S2) 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 복사
-1dp에서는 연속 합을 구하는 문제가 꽤 많이 나와서 열심히 연습중이다.
이번 문제는 처음에 다음과 같은 알고리즘을 생각해냈다.
이런식으로 계산하면서 배열에 각 원소가 리스트인 형태로 저장되었고, 이 리스트에 대한 공식은 다음과 같이 나왔다.
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에 대한 자신감도 없고, 특히 점화식을 정확히 세우는것이 조금 어렵기 때문에 더 풀어봐야 할것같다.