백준 - 1912번 - 연속합[파이썬]

1. 문제 출처

백준 - 1912번: 연속합 문제로 이동하기

 

 

우선 링크로 가서 문제를 보도록 하자. 

2. 문제 설명

문제

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

정답: 33

 

테스트 케이스2

10

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

정답: 14

 

3. 문제 풀이 

(1) 논리의 구성 - 동적 계획법(DP)

 

이 문제의 핵심은 최대 계산 값을 계속 기록하면서, 최대한 빠른 시간 안에 해결하는 것입니다.

 

흔히 말하는 Memorization(기억법)이라고 하죠. 대표적인 DP 스킬 중에 하나인데요, 여기서 이게 어떻게 쓰이는지 한 번 보도록 하겠습니다. 

 

 1) 손코드의 계획 

 

첫 번째. i번째 데이터 이전까지 합을 계산해 봤을 때 최대값을 지속적으로 기록한다. 

 - 원칙1. 이전까지의 합이, 그냥 i번째 숫자보다 작은 경우 이전의 기록들은 무의미하다.

            그러니 그냥 i번째 숫자를 최대값으로 설정한다. 

 

 

(2) 실제 구현코드

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

  - 반복문의 시작을 1에서 하는 이유

 : 문제 풀이의 핵심은 "이전까지 모든 숫자의 합 중 최대값"을 그때그때 기록하는 것입니다. 

데이터의 시작점인 0번 인덱스는 이전까지의 합이 0 자신 자체이기 때문에 아무런 필요가 없는 것이죠. 

그래서 반복문의 시작은 1부터 합니다. 

 

- m[i] = max(  m[ i ],    m[ i ] + m[ i-1 ])  -> i번 째 데이터를 업데이트하는 이유

: i번째 인덱스는 핵심코드의 논리인 "이전까지 모든 숫자의 합 중 최대값"이기 때문에 수정을 해 주어야 합니다. 

 

예를 들어서 10번째 인덱스를 계산할 차례인데, 9번째 인덱스까지의 모든 경우의 수를 다시 계산하면 시공간 복잡도가 낭비되는 단점이 있죠.

 

그래서 그냥 data의 9번째 값 자체를 이때까지 나온 모든 경우의 수 중에서 가장 최대값으로 업데이트를 하는 것입니다. 

이 부분은 아래의 시뮬레이션을 보면 이해가 빠르실 거에요. 

 

 

 

(3) 코드로 돌아가는 테스트 케이스 시뮬레이션

 1) 기본 데이터 준비 

n 

m = [ 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 ]

 

첫 번째 Loop. i = 1

 

m[1] = max( -4, -4+ 10 = 6 ) -> m[1] = 6

 

m = [ 10, 6, 3, 1, 5, 6, -35, 12, 21, -1 ]

 

이때 6은 이전까지 연속된 합 중 최대값을 기록한 것입니다. DP - Memorization

 

두 번째 Loop. i = 2

 

m[2] = max( 3, 3+6= 9) -> m[2]  = 9

 

m = [ 10, 6, 9, 1, 5, 6, -35, 12, 21, -1 ]

 

9 또한 이전가지 연속된 합 중 최대값을 기록한 것입니다.DP - Memorization

 

이렇게 루프가 다 돌았을 때 나오는 데이터의 경우의 수는 아래와 같습니다.

 

m = [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

 

그래서 m 중에서 가장 큰 수는 33이기에 정답이 되는 것입니다. 

 

 

이런 식으로  자신의 논리가 정확한지 확인하기 위해서는 손으로 하나하나 테스트 케이스를 적어가면서, 기본적인 프로그래밍 원리에 부합하는 확인하는 것도 좋은 방법이랍니다.