BOJ(백준) 1912[연속합]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 1912번을 풀어보겠습니다. 이 문제는 주어진 수열에서 연속된 부분 수열의 합이 최대가 되는 값을 찾는 문제입니다.

 

문제 URL: https://www.acmicpc.net/problem/1912

 

1. 문제 설명

주어진 수열에서 연속된 부분 수열의 합이 최대가 되는 값을 찾아야 합니다. 예를 들어, 주어진 수열이 [2, 1, -4, 3, 4, -4, 6, 5, -5, 1]인 경우, 최대 합을 갖는 연속 부분 수열은 [3, 4, -4, 6, 5]로서 그 합은 14입니다.

 

2. 접근법

1. 수열의 크기 n을 입력받습니다.

2. 수열을 입력받아 리스트로 저장합니다.

3. 누적 최대 합(prefix sum)을 이용하여 효율적으로 계산합니다:

• 각 원소를 누적하면서 현재 원소를 포함하는 최대 합을 계산합니다.

• 현재 원소를 포함하지 않는 경우와 포함하는 경우 중 최대값을 선택합니다.

4. 누적 최대 합 리스트에서 최대값을 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 첫 번째 줄에서 n을 입력받음 (수열의 크기)
n = int(input())
# 수열을 입력받아 리스트로 저장
arr = list(map(int, input().split()))

# 누적 최대 합을 담을 리스트 선언, 길이는 n+1로 설정
prefix = [0] * (n + 1)

# 누적 최대 합 계산
for i in range(n):
    # 이전까지의 누적합에 현재 원소를 더한 값과 현재 원소 중 최대값을 선택
    prefix[i + 1] = max(prefix[i] + arr[i], arr[i])

# 누적합 리스트에서 첫 번째 원소를 제외한 값들 중 최대값을 출력
print(max(prefix[1:]))

 

4. 코드 설명

1. 입력 처리

• 첫 번째 줄에서 n을 입력받습니다.

• 두 번째 줄에서 n개의 수를 입력받아 리스트로 저장합니다.

2. 누적 최대 합(prefix sum) 계산

• 누적 최대 합을 담을 리스트 prefix를 선언합니다. 길이는 n+1로 설정합니다.

• 각 원소를 누적하면서 현재 원소를 포함하는 최대 합을 계산합니다.

• prefix[i + 1]는 prefix[i] + arr[i]와 arr[i] 중 최대값을 선택하여 저장합니다.

3. 최대 합 계산

• 누적합 리스트에서 첫 번째 원소를 제외한 값들 중 최대값을 찾아 출력합니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_03_02_1912.py at main · pcy4196/coTest