백준 | 13398번. 연속된 정수의 합 구하기 - DP 문제

🟦 백준 13398번. 연속된 정수의 합 구하기

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

13398번: 연속합 2

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

이 문제는 A[] 배열에 음수가 포함이 되고 한개의 수를 제거할 수 있는 선택권이 존재한다.

이 선택을 할지 말지는 i값을 제거했을 때의 합 vs i값 포함했을 때의 합 중 최댓값을 비교하여 결정할 거다.

1) A[] 배열에는 기존 입력 데이터들을 저장한다.

2) 포인트는 ‘연속된 합’ max 값 (단, 1개 제거는 선택) 이다.

여기서 사용할 배열은 L[], R[] 배열이다.

우선, L[] 배열 세팅 방식

L[i] : 오른쪽 방향으로 i값 포함한 최대 연속합 저장용

L[0] = A[0] 값으로 초기화 
for(int i=1 ~ N) 
  L[i] = Math.max(A[i], L[i-1] + A[i]);
  //즉, 그냥 현재 A[i]값 vs 직전 L값합에 현재 i를 포함값 
             중에서 더 큰 값으로 세팅하는 거다. 
  result = Math.max(result, L[i]);// 여기에는 하나도 제거 안했을 때 최댓값을 저장 

R[]배열 세팅 방식

R[N-1] = A[N-1] //끝 값을 세팅 
for(int i=N-2 ~ 0) //거꾸로 돌면서 
 R[i] = Math.max(A[i], R[i+1] + A[i]);
//즉, 기존 i값 vs R의 값 + A[] 비교하여 최댓값 저장 
}

1. L[]배열에는 왼→오 방향으로 각 i를 포함하였을 때 최대 연속 합을 저장했다. 연속합 보다 기존 값이 더 크면 그냥 기존값으로 세팅하는 방식으로.
2. R[]배열에는 오→왼 방향으로 각 i를 포함하였을 때 최대 연속합을 저장했다.
3. 이제 마지막으로 해야 할 일은 각각의 i값을 제거하였을 때

L[i-1] + R[i+1] 값이 기존 result (max) 보다 큰 경우 갱신해주는 일이다.

이 작업을 통해 1개의 값을 제거했을 때 더 큰 값이 나타나면 그렇게 제거하는 선택을 구현한다.

---

풀이(코드) :

result + \n 개행 문자 넣어줘야 정답 처리 된다.

1) BufferedReader + Writer 버전

package to_0714_7;
import java.io.*;
import java.util.StringTokenizer;

public class Main {
  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());
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    // 오른쪽 방향으로 index를 포함한 최대 연속 합 구하기.
    int[] L = new int[N];
    L[0] = A[0];
    int result = L[0];
    for (int i = 1; i < N; i++) {
      L[i] = Math.max(A[i], L[i - 1] + A[i]);
      result = Math.max(result, L[i]); // 하나도 제거 하지 않았을 때를 기본 최대값으로 저장
    }
    // 왼쪽 방향으로 index를 포함한 최대 연속 합 구하기.
    int[] R = new int[N];
    R[N - 1] = A[N - 1];
    for (int i = N - 2; i >= 0; i--) {
      R[i] = Math.max(A[i], R[i + 1] + A[i]);
    }
    // L[i - 1] + R[i + 1] 두개의 구간합 배열을 더해주면 i번째 값을 제거한 효과를 얻음
    for (int i = 1; i < N - 1; i++) {
      int temp = L[i - 1] + R[i + 1];
      result = Math.max(result, temp);
    }
    bw.write(result + "\\n");
    bw.flush();
    bw.close();
    br.close();
  }
}

---

2) Scanner + System.out.println() 이떄 개행 포함

import java.util.Scanner;

/*연속합 다시 풀이 */
public class Main {
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int N =kb.nextInt();
		
		int[] A = new int[N];
		//데이터 입력받기 
		for(int i=0; i<N; i++) {
			A[i]= kb.nextInt();
		}
		int result = A[0];//얘로 i포함한 연속합 최댓값 찍을 거임 
		//L[] 데이터 처리 
		int[] L = new int[N];
		L[0]= A[0];
		for(int i=1; i<N; i++) {
			L[i] = Math.max(A[i], L[i-1]+A[i]);
			result = Math.max(result, L[i]);
		}		
		//R[] 데이터 처리 
		int[] R = new int[N];
		R[N-1] = A[N-1]; //오른쪽 끝 데이터 초기화 
		for(int i=N-2; i>=0; i--) {
			R[i]= Math.max(A[i], R[i+1]+A[i]);
		}
		//이제 i로 전체 순회하며 값 찍고, 그 값 제외한 값이 기존 result보다 크면 갱신
		for(int i=1; i<N-1; i++) {
			int tmp = L[i-1] + R[i+1];
			result = Math.max(result, tmp);
		}
		System.out.println(result + "\\n"); //개행문자 포함하여 답 출력 
	}
}