[Baekjoon] 13398_연속합 2

Gold V

문제(출처: https://www.acmicpc.net/problem/13398)

---

< 연속합 2 >

 

문제 풀이 

 

처음에는 수열 값 중에서 음수 중 가장 작은 값을 제거하는 방법으로 구현했다. 하지만 이렇게 구현할 경우 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구할 수 없다. 

 

그래서 두 번째 방법으로는 모든 수를 한 번씩 제거하는 경우로 배열을 n x n 크기로 만들어서 구현했다. 하지만 이 경우에는 n의 범위가 1 이상 100000 이하이므로 메모리 초과가 발생했다.

 

마지막으로 구현한 방법은 배열을 2 x n 크기로 만들어 0번째 행은 수를 제거하지 않은 경우, 1번째 행은 수를 하나 제거한 경우로 구현했다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _13398_ { // 연속합 2

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		int arr[] = new int[n];
		int answer[][] = new int[2][n];
		st = new StringTokenizer(bf.readLine());

		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr[i] = num;
		}

		int result = arr[0];

		answer[0][0] = arr[0];
		for (int i = 1; i < n; i++) {
			answer[0][i] = Math.max(answer[0][i - 1] + arr[i], arr[i]);
			answer[1][i] = Math.max(answer[0][i - 1], answer[1][i - 1] + arr[i]);

			result=Math.max(answer[0][i], result);
			result=Math.max(answer[1][i], result);
		}
		System.out.println(result);
	}
}

변수)
n : 수열 개수
arr : 수열 
answer : 연속된 몇 개의 수를 선택해서 구할 수 있는 합
result : 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합

 

수열을 입력받아 연속된 몇 개의 수를 선택해서 구할 수 있는 합을 구한다.

answer의 0번째 행에는 수를 제거하지 않는 경우를 저장하고 1번째 행에는 수를 하나 제거하는 경우를 저장한다. 저장한 값 중에서 가장 큰 값을 출력한다.

---

---