관련글
Dynamic Programming 관련 포스팅은 여기를 참조
관련 문제인 1912번(연속합) 관련 포스팅은 여기를 참조
1. 개요
문제의 링크는 여기를 참조
이 문제는 배열의 연속합을 구하되 특정 값을 제거하거나 제거하지 않을 수 있는 옵션이 붙은 문제이다.
2. 풀이
우선 문제를 이해하자. 배열 내에서 단순히 값을 몇 개 뽑아서 더하는 것이 아니라 연속합 중 최대의 경우를 구해야 한다.
연속합은 1개만 있어도 연속합이 될 수 있다.
아래와 같은 배열이 있을 때를 예시로 조금만 알아보자. arr[i]는 원 배열이고, sum[i]는 연속합이 최대가 되는 경우의 배열이다.
인덱스 i | 0 | 1 | 2 | 3 |
arr[i] | 10 | -12 | 30 | -8 |
sum[i] | 10 | -2 | 30 | 22 |
sum[i]을 보며 왜 저렇게 되었는지 알아보자.
index=0일 때, 현재 위치 기준 최대 연속합은 자기 자신 뿐이므로 sum[0] = 10
index=1일 때, 현재 위치 기준 최대 연속합은 자기 자신 보다는 이전과의 합이므로 10+(-12)가 되어 sum[1] = -2
index=2일 때, 현재 위치 기준 최대 연속합은 자기 자신이 이전과의 합보다 크므로 sum[2] = 30
index=3일 때, 현재 위치 기준 최대 연속합은 자기 자신 보다는 이전과의 합이므로 30+(-8)이 되어 sum[3] = 22
즉, 현재 위치 기준 최대 연속합은 이전 연속합과 더하거나 더하지 않거나 2가지 중 한 가지가 된다.
위를 기반으로 점화식을 만들 수 있으며, 각 부분에서 이전의 결과가 반복적으로 사용되고 해당 최적 결과값이 그대로 사용되니 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족하여 DP로 풀 수 있다.
그런데, 이 문제는 한 가지의 옵션이 더 있다. 중간에 값을 하나 제외해도 된다는 것!
기본적으로 생각할 수 있는 아이디어는, 각 위치의 숫자를 탐색하면서 이전의 숫자들 중 일부를 제외하는 경우를 모두 체크하는 경우가 있을 수 있다.
하지만 그 경우, 2중 반복문을 활용하기에 $O(N^2)$의 시간복잡도가 도출되어 최대 10만개의 숫자라면 시간초과가 발생한다.
사실 이 문제는 간단한 아이디어를 통해 해결할 수 있다.
현재 값을 기준으로 좌측의 연속합, 우측의 연속합을 더하면 현재 값을 제외한 결과값 중 최대의 값을 구할 수 있게 된다.
그렇다면, DP로 풀 수 있으니 저장할 State의 정의를 한 번 세워보자. 여기서 State는 배열의 길이에 따른 위치 뿐이다. 아래와 같을 것이다. 따라서 1차원으로 저장할 수 있다.
좌측에서 부터의 연속합은 left, 우측을 right 배열이라고 바꿔서 쓰자.(DP 문제임을 강조하기 위해..)
정의 ▼
left[N] = 위치 N에서의 좌측에서부터의 연속합의 최대값
right[N] = 위치 N에서의 우측에서부터의 연속합의 최대값
기저 상태와 점화식을 알아보자.
기저 상태는 좌측은 index가 0일 때, 우측은 N-1일 때이다. 해당 경우에는 원 배열의 값을 그대로 적용한다.
기저 상태 : left[0] = arr[0], right[N-1]=arr[N-1]
점화식은 이전의 연속합과 합하거나 하지 않거나 이므로 그 중 더 큰 값으로 구한다.
점화식 :
left[N] = Math.max(left[N-1] + arr[N], arr[N])
right[N] = Math.max(right[N+1]+arr[N], arr[N])
그러면 결과는 아래와 같이 구할 수 있다. 현재 위치의 값을 빼고 계산하거나 값을 포함 시켜 계산하는 경우를 모두 연산해야 한다.
결과 ▼
result[N] = MAX(left[N-1] + right[N+1], left[N])
3. 코드
아래의 코드를 통해 정답을 알아보자.
1) Bottom-up 방식
import java.io.*;
public class Main {
static int arr[];
static int left[];
static int right[];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
arr = new int[n];
left = new int[n];
right = new int[n];
String line[] = br.readLine().split(" ");
int result = Integer.MIN_VALUE;
// 우선 좌측에서 시작하는 연속합의 최대 경우를 구함
for(int i=0; i < n; i++){
arr[i] = Integer.parseInt(line[i]);
if(i == 0) {
left[i] = arr[i];
} else {
left[i] = Math.max(left[i-1] + arr[i], arr[i]);
}
// 특정 값을 빼지 않고도 최대값이 되는 경우가 있으니 이 또한 고려
result = Math.max(result, left[i]);
}
// 우측에서 시작하는 연속합의 최대 경우를 구함
for(int i=n-1; i >= 0; i--){
if(i == n-1){
right[i] = arr[i]; continue;
}
right[i] = Math.max(right[i+1] + arr[i], arr[i]);
}
// 특정 index를 빼고 좌 우측의 합으로만 수행하기
for(int i=1; i < n-1; i++){
result = Math.max(result, left[i-1] + right[i+1]);
}
bw.write(String.valueOf(result));
br.close();
bw.flush();
}
}
2) Top-Down 방식
import java.io.*;
public class Main{
static int[] arr;
static int[] left;
static int[] right;
static int n; // 여기에 써야 우측 부터 시작 시 n에 바로 접근(혹은 parameter로 전달해도됨)
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
String s[] = br.readLine().split(" ");
arr = new int[n];
left = new int[n];
right = new int[n];
for(int i=0; i < n; i++){
arr[i] = Integer.parseInt(s[i]);
left[i] = Integer.MIN_VALUE; // Top-Down에서는 반환 조건을 위해 초기에 최소값으로 지정
right[i] = Integer.MIN_VALUE;
// 문제에서 -1000 ~ 1000까지만 나오고 100,000개 이므로 최소 -1억이다.
// 이를 기반으로 아래에서 조건식 지정
}
topDown_left(n-1);
// 특정 값을 빼지 않고도 최대값이 경우가 있을 수 있다!
int result = Integer.MIN_VALUE;
for(int i=0; i < n; i++){
result = Math.max(result, left[i]);
}
topDown_right(0);
// 특정 값을 빼고 최대값이 나오는 경우를 위해 추가
for(int i=1; i < n-1; i++){
result = Math.max(result, left[i-1] + right[i+1]);
}
bw.write(String.valueOf(result));
br.close();
bw.flush();
}
// Top-Down 방식 좌측에서 시작
public static int topDown_left(int k){
// 여기서 반환 조건식을 지정함
// 값이 최소값이 아니거나 k=0이면 반환
if(k == 0) return left[k] = arr[k];
if(left[k] > Integer.MIN_VALUE) return left[k];
// 재귀를 통해서 값을 구해온다.
return left[k] = Math.max(topDown_left(k-1) + arr[k], arr[k]);
}
// Top-Down 방식 우측에서 시작
public static int topDown_right(int k){
// 여기서 반환 조건식을 지정함
// 값이 최소값이 아니거나 k=0이면 반환
if(k == n-1) return right[k] = arr[k];
if(right[k] > Integer.MIN_VALUE) return right[k];
// 재귀를 통해서 값을 구해온다.
return right[k] = Math.max(topDown_right(k+1) + arr[k], arr[k]);
}
}
읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.
'알고리즘 풀이(Problem Solving) > Dynamic Programming' 카테고리의 다른 글
알고리즘 풀이 - 백준 17404(RGB거리 2, DP) (0) | 2021.01.17 |
---|---|
알고리즘 풀이 - 백준 2133(타일 채우기, DP) (0) | 2021.01.16 |
알고리즘 풀이 - 백준 11054(가장 긴 바이토닉 부분 수열 ,DP) (0) | 2021.01.16 |
알고리즘 풀이 - 백준 11722(가장 긴 감소하는 부분 수열, DP) (0) | 2021.01.16 |
알고리즘 풀이 - 백준 11055(가장 큰 증가 부분 수열, DP) (0) | 2021.01.16 |