알고리즘

[백준] 1912 연속합 - 실버 2

swanzzz 2025. 5. 20. 22:41
반응형

[오늘의 문제]

https://www.acmicpc.net/problem/1912

[오늘의 학습 키워드]

  • DP, 구현

1. 문제설명

 

N개의 정수로 이루어진 수열에서 연속해서 수들의 합을 구할 때 가장 큰 수를 구하는 방법을 작성하는 문제 입니다.

[제한사항]

  • 시간 제한 1초
  • 메모리 제한 128MB
  • 1 ≤ n ≤ 100,000
  • 주어지는 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수

2. 접근방식

 

이번 문제는 쉽게 생각하면 해결이 되는 문제입니다.

 

수들은 음수 또는 양수로 주어집니다.

 

-1000 부터 1000 사이의 수가 주어지니 0도 주어지겠죠

 

수열이 주어지면 DP 테이블을 만들고 DP 테이블에 이전 값들의 합과 현재값을 비교하는 겁니다.

 

그 두 수중 더 큰값으로 DP 테이블을 바꿔가면 DP 테이블을 채워나가면 되겠죠

 

그렇게 DP 테이블을 이용해 누적합을 구해 나가면서 조건에 맞나 비교해주면 되겠죠

위 그림처럼 N이 주어지고 DP 테이블을 생성했을 때 두개를 비교하는 겁니다.

 

기본적으로 DP[0] 은 nums[0] 과 동일해야 누적합을 만들 수 있겠죠

 

DP[0] 은 DP[0] 이전의 값들을 누적해서 더한값이라고 생각할 수 있겠죠

 

DP[1] 은 DP[0] 에 nums[1] 값을 더한 값이 더 큰지 아니면 그냥 nums[1]이 더 큰지 둘 중 비교를 해줍니다.

 

위 경우 DP[0]은 2이고 nums[1] 은 1로 두 값을 더하면 3이고

 

nums[1] 은 1로 두 값을 비교하면 3이 더 크죠 따라서 DP[1] 은 3이 됩니다.

 

 

지금의 경우는 3에 -4를 더한값이 더 큰지, -4가 더 큰지 비교하게 됩니다.

 

당연히 3에 -4를 더하면 -1로 -4보다 더 크기 때문에 -1이 더 큰값이 되겠죠

 

이 경우를 일반화 시켜보면 DP[i] 번째 값은 결국 DP[i - 1] 에 nums[i] 번째 값을 더한게 더 큰지 아니면 nums[i] 가 더 큰지 비교해

 

서 누적하는 경우가 되겠죠 

 

여기서 생성된 점화식이

 

DP[i] = max(DP[i - 1] + nums[i], nums[i]) 가 되겠죠 이를 코드로 구현해 보았습니다.

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
nums = list(map(int, input().split()))

# DP 테이블 생성 및 초기화
DP = [0] * N
DP[0] = nums[0]

# 점화식 토대로 누적값 채우기
for i in range(1, N):
    DP[i] = max(nums[i], DP[i - 1] + nums[i])

# 가장 큰 값 출력
print(max(DP))

[코드설명]

 

이번 코드의 경우 DP 테이블과 nums 테이블의 인덱스를 맞출 필요가 없기 때문에 DP 테이블도 N개 생성하고

 

1부터 N까지 탐색을 실시해 주었습니다.

 

앞서 구성한 점화식을 그대로 코드로 구현해 주었고 이중 가장 큰 값을 가지는 누적값을 출력해 주었습니다.

4. 결과

[회고]

이번 문제의 경우 가장 긴 증가하는 부분 수열 문제와 동일하게 접근했다가 처음에 틀렸던 문제 입니다.

 

이번문제의 제한사항이 N이 10만이라 2중 반복문을 사용하면 최대 10만 x 10만 정도가 되어서 시간 초과가 발생했을 겁니다.

 

그래서 누적합을 구하는 과정에서 시간을 줄이고자 음수는 제외한 양수의 경우만 더해 출력해 보았는데 

 

이렇게 코드를 구성하니 예제 2번에서 막히더라구요

 

예제 2번의 경우 음수를 포함해서 5개의 수를 더했을 때 가장 큰 연속합이 이루어 졌기 때문입니다.

 

따라서 모든 누적합을 구하는데 지금의 누적합에 새로운 값을 더하는게 큰지, 아니면 더하지 않은 자기 자신이 큰지만 비교해서 문

 

제를 풀어보았고 이렇게 하니 제대로 출력이 되었습니다.

 

여러번 검증을 거치며 시간을 줄이는 방법을 찾으려 했는데 이렇게 작성한 코드는 결국 O(N) 시간이 걸려서 크게 수정하지 않고 정답을 맞출 수 있었습니다.

반응형