BOJ 1912 연속합
https://www.acmicpc.net/problem/1912
시간 1초, 메모리 128MB
input :
- n (1 ≤ n ≤ 100,000)
- n개의 수 (-1,000 <= 수 <= 1,000)
output :
- 답을 출력
조건 :
- 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합(단, 수는 한 개 이상 선택)
- ex ) {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 이라는 수열. 정답은 12+21인 33
시간 복잡도가 문제긴 한데... 이중 반복문 해서
i를 인제 체크 하려는 수열의 길이
j는 수열의 시작하는 지점.
으로 구성해서 계산을 하면 되지 않을까?
import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
ret = -999999999
for i in range(1, n):
for j in range(n):
if j + i > n:
continue
ret = max(ret, sum(data[j : j + i]))
print(ret)
그러면 어떻게 해야 하나...
연속적.
수열의 경우 고르는 숫자들 모두 연속적으로 붙어있다.
그러면 다음 숫자를 만날 경우 두 가지 경우의 수가 발생.
- sum(현재까지 합) + current
- current
1번과 같이 합한 경우가 큰지. 아니면 자기 혼자가 큰지 비교를 한 후
ret 리스트에 저장을 하자.
리스트에 저장을 하면. 어느 idx에서 최댓값을 가지고 있는지 알 수 있어서 마지막에 이를 출력해주면 된다.
import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
ret = [data[0]]
for i in range(1, n):
ret.append(max(ret[i - 1] + data[i], data[i]))
print(max(ret))
현재까지의 합의 경우 ret[i - 1]에 존재하기 때문에 꺼내 쓰자.
오늘도 하나 배워갑니다...
Author And Source
이 문제에 관하여(BOJ 1912 연속합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-1912-연속합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)