개발일지/Algorithm
백준 - 1912 연속합 [DP]
E-room
2023. 9. 20. 17:34
728x90
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
1. 간단 요약
해당 문제는 수열이 주어지면, 해당 수열의 부분연속수열의 합중 가장 큰 값을 구하는 문제이다.
2. 접근 방법
- 순차적으로 값을 더한다.
- 다음에 올 숫자가 이득인지 손해인지를 판단한다.
- 현재까지의 값 + 수열의 현재 인덱스의 값 vs 수열의 현재 인덱스의 값을 비교하여 더 큰 값을 취한다.
예를 들어 아래와 같은 수가 주어질 경우
-4는 음수이지만 10과 합하면 6이다.
해당 값과 3을 더하면 9이므로, 3보다 크기때문에 손해가 아니므로 취한다.
아래처럼 21과 -35를 합하면 -14가 된다.
-14와 12를 더하면 -2이므로 12보다 작다. 손해이므로 버리고 12부터 새로 출발한다.
이를 반복한다.
모두 반복했을 경우, 33이 가장 큰값이 된다.
3. 파이썬
n = int(input())
arr = list(map(int, input().split()))
dp = [0 for _ in range(n + 1)]
for i in range(n):
dp[i + 1] = max(dp[i] + arr[i], arr[i])
print(max(dp[1:]))
4. 자바
아래는 dp 배열을 생성하는 대신 현재 값을 저장하는 방식으로 해주었다.
조건에서 -1000이 가장 작은 값이라 명시되어 있으므로 -1000으로 초기화해주었다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int now = -1000;
int max = -1000;
for (int i = 0; i < n; i++) {
int num = Integer.parseInt(st.nextToken());
now = Math.max(now + num, num);
max = Math.max(max, now);
}
System.out.println(max);
}
}
5. 깃허브 전체 코드
728x90