문제
13398번: 연속합 2
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
알고리즘
다이나믹 프로그래밍 (DP)
풀이
[2][n+1] 크기의 2차원 배열 dp를 선언하고 다음과 같이 값을 저장한다.
dp[0][i] = 값을 제거한 적 없는 i번째 수까지의 최대 연속합
dp[1][i] = 값을 제거한 적 있는 i번째 수까지의 최대 연속합
i 번째 수를 num이라고 할 때,
dp[0][i] 는 dp[0][i-1] 가 0보다 작다면 이전까지의 연속합을 버리고, num 부터 새로 시작하는 것이 더 큰 값을 만들 수 있다.
dp[0][i] = Math.max(dp[0][i - 1] + num, num);
dp[1][i] 는 dp[1][i-1] + num 보다 dp[0][i-1] 가 더 클 경우 이번 num을 제거하는 것으로 더 큰 값을 만들 수 있다.
dp[1][i] = Math.max(dp[1][i - 1] + num, dp[0][i - 1]);
따라서 수열을 끝까지 탐색하며 dp[0][i], dp[1][i] 값 중 최댓값을 갱신하여 출력한다.
* 문제에서 최대 1개의 수를 선택해야한다는 조건이 있기 때문에 dp[0][1] 을 arr[1]로, max 또한 arr[1]로 초기화해야한다.
dp[0][1] 을 초기화 하지않으면 음수로만 이루어진 경우 0 을 답으로 출력하고,
max 값을 Integer.MIN_VALUE 등 다른 값으로 초기화해두면 수열 크기가 1인 경우 MIN_VALUE를 그대로 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] dp = new int[2][n + 1];
int[] arr = new int[n + 1];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= n; i++)
arr[i] = Integer.parseInt(st.nextToken());
int max = arr[1];
dp[0][1] = arr[1];
for (int i = 2; i <= n; i++) {
int num = arr[i];
dp[0][i] = Math.max(dp[0][i - 1] + num, num);
dp[1][i] = Math.max(dp[1][i - 1] + num, dp[0][i - 1]);
max = Math.max(max, Math.max(dp[0][i], dp[1][i]));
}
System.out.println(max);
}
}
'Algorithm > 백준(BOJ)' 카테고리의 다른 글
[백준] 1707. 이분 그래프 (Java) (0) | 2022.12.02 |
---|---|
[백준] 13023. ABCDE (Java) (0) | 2022.12.02 |
[백준] 11722. 가장 긴 감소하는 부분 수열 (Java) (1) | 2022.12.02 |
[백준] 2156. 포도주 시식 (Java) (0) | 2022.12.02 |
[백준] 11057. 오르막 수 (Java) (0) | 2022.12.02 |