[백준] 1912 - 연속합

g_choi·2023년 3월 27일
0

PS 풀이

목록 보기
1/1

문제 풀러가기


주의

공부를 한 이후 스스로 풀이한 것을 적어둔 게시물입니다. 치팅 행위에 대한 책임을 지지 않습니다.

풀이

가장 큰 연속합을 구하는 알고리즘을 구하는 문제다. 문제에서 제시한 조건은

1개 이상의 수를 무조건 포함하기
수열의 원소 개수 n은 최대 10만이 될 수 있다

파이썬은 1초에 최대 백만번의 연산이 가능하다고 가정해야하니 아마 시간복잡도 O(n)으로 풀어야 시간초과가 뜨지 않을 것이란 걸 알 수 있다. 즉, for문은 한 번 이상 중첩하면 안된다.

다음을 보자.

길이가 1인 수열은 당연하지만 0번째 원소 자체가 가장 큰 연속합이다.

n = 1
seq = [10]
이런 경우 가장 큰 연속합은 10

길이가 2인 수열일 때, 가장 큰 연속합은 3가지 중 하나일 것이다.
1. 0번 째 원소 ex> [10, -4]
2. 1번 째 원소 ex> [-10, 30]
3. 0번 + 1번 ex> [10, 20]
여기서 1번의 경우는 어디서 본 거 같지 않은가? 그렇다! 위에 길이가 1인 수열 경우를 이야기 하는 것이다! 즉, 우린 이를 다이나믹 프로그래밍으로 풀 수 있다고 대략적으로 감을 잡을 수 있다.
뭔 소린지 잘 모르겠더라도 살짝 기억만 해두고, 일단 계속해보자면 2번과 3번의 경우는 어렵지 않게 아래의 코드로 구할 수 있을 것이다.

n = 2

case 1
seq = [10, -4]
이런 경우, 가장 큰 연속합은 10

case 2
seq = [-10, 30]
이런 경우, 가장 큰 연속합은 30

case 3
seq = [10, 20]
이런 경우, 가장 큰 연속합은 30

즉, 길이가 2인 가장 큰 연속합은 
=> max(case 2, case 3) => max(seq[0] + seq[1], seq[1])

여기서 하나 이상하다고 생각했을 수도 있는데, 아래의 max()로 2번 경우과 3번 경우 중 어느 것이 더 큰 지 계산하였지만, 저 max()에는 1번의 경우를 고려하지 않고 있다. 그 이유는 위에 경우들 중 1번은 길이가 1인 수열일 때도 구해지는 경우이기 때문이다. 잘 보면 만약 1번 경우(0번 째 원소가 가장 큰 연속합일 때)는 그 결과가 길이가 1인 수열을 계산할 때 이미 나온 결과라고 생각하지 않는가? 즉, 우린 길이가 2인 수열을 구할 때 길이가 1인 수열에서 1번째 원소를 더해보고 그게 1번 째 원소보다 크면 기억해두고(이게 2번의 경우), 아니면 1번 째 원소 자체가 가장 큰 연속합이란 의미이다(이게 3번의 경우).

위에서 장황히 설명한 내용을 코드로 간단히 보자

max(dp[0] + seq[1], seq[1])

그럼 우린 길이가 2인 수열에서의 가장 큰 연속합을 구할 수 있고, 이를 기억해두었다가 아까 길이가 1인 수열의 경우와 비교하여 또 max()를 해주면 길이에 상관없이 부분수열로 구할 수 있는 가장 큰 연속합을 구할 수 있게 된다.

예제로 따라가보자.

n = 1
seq = [10]
dp = [10]
결과 = 10

n = 2
seq = [10, -4]
dp = [10, 6]
결과  = max(dp) = 10

n = 3
seq = [10, -4, 12]
dp = [10, 6, 18]
결과 = max(dp) = 18

n = 4
seq = [10, -4, 12, -35]
dp = [10, 6, 18, -17]
결과 = max(dp) = 18

여기까지 왔으면 모든 코드를 작성해보자.

정답코드

n = int(input())
seq = list(map(int, input().split()))
dp = [0] * n

#길이가 1인 경우
dp[0] = seq[0]

#길이가 n인 경우 (n >= 2) 
for i in range(1, n):
    a = dp[i - 1] + seq[i] # 이전까지의 수열과 새로운 원소의 합
    b = seq[i] # 이번 원소
    dp[i] = max(a, b) # 새로운 원소가 이전보다 더 크면 이전 수열은 필요없음

print(max(dp))

여담

나름대로 좀 풀어서 작성할려다보니 해설이 문제보다 어려워 진 게 아닌가 싶다 ㅎㅎ.... 다음에는 조금 더 쉽게 작성해봐야겠다. 오류 수정은 언제나 환영입니다!

profile
해외에서 공부중인, 다양한 걸 배울려 하는, 항상 모자름을 느끼기에 성장하는 학생 :D

0개의 댓글