[1912번] 연속된 합 JAVA☕

www.acmicpc.net/problem/1912

1912번: 연속합

알고리즘 [접근 방법]

문제 예제들을 그대로 적용해보면 이렇다.

 

첫 번째 예제는 아래와 같다. (배열로 표현함)

 

여기서 연속된 수를 선택하여 뽑아내면 다음과 같다.

 

 

두 번째 예제를 보자.

 

 

 

두 번째 예제를 보면 index5 에 -4 라는 음수가 들어있지만 이를 포함하여 index7까지 연속으로 택하여 합한 것이 최댓값임을 알 수 있다.

 

즉, 포인트는 음수 양수 상관없이 '연속적으로 선택한 수의 합'이 최댓값이 되는 수를 찾으면 되는 것이다. 즉, 메모이제이션은 이전까지 탐색했던 값과 현재 위치의 값을 비교하여 큰 값을 저장하면 되는 것이다.

 

 

Top-Down 방식인 재귀로 구현하자면 개괄적으로 다음과 같다.

static int recur(int N) {
 
	// 탐색하지 않은 인덱스라면
	if(dp[N] == null) {
 
		// (이전 배열의 누적합 + 현재 값)과 현재 값을 비교하여 최댓값을 N위치에 저장
		dp[N] = Math.max(recur(N - 1) + arr[N], arr[N]);
		
	}
		
	return dp[N];
}

반대로 Bottom-Up으로 하면 위 코드를 반복문으로 다음과 같이 구현할 수 있다.

for (int i = 1; i < N; i++) {
	dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
}

그러면 메모이제이션이 된 dp배열에는 각 인덱스까지의 최댓값이 저장되어있다는 의미다. 예로들어 dp[3]이라 하면 dp[0] ~ dp[3] 에서 연속으로 선택한 부분 수열의 최댓값이 저장되어있다는 의미다.

 

그리고 나서 dp 배열의 원소들 중 가장 큰 값을 찾아서 출력하면 되는 것이다.

 

이 때 dp배열의 최댓값을 정렬 또는 하나하나 탐색하여 찾아내는 방법도 있지만, 처음부터 아예 재귀 또는 반복문안에 max변수를 하나 두어 최댓값을 갱신 하는 것이 더욱 효율적일 것이다.

---

풀이 및 코드

- 방법 1 : [Scanner + Top-Down]

import java.util.Scanner;
 
public class Main {
	
	static int[] arr;		// 배열 
	static Integer[] dp;		// 메모이제이션 할 dp
	static int max;			// 최댓값 변수 
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		arr = new int[N];
		dp = new Integer[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
		/*
		 * dp[0]은 첫 원소로 이전에 더이상 탐색할 것이 없기 때문에
		 * arr[0] 자체 값이 되므로 arr[0]으로 초기화 해준다.
		 * max또한 첫 번째 원소로 초기화 해준다.
		 */
		dp[0] = arr[0];
		max = arr[0];
		
		// dp의 마지막 index는 N-1이므로 N-1부터 Top-Down 탐색 
		recur(N - 1);
		
		System.out.println(max);
	}
	
	static int recur(int N) {
		
		// 탐색하지 않은 인덱스라면
		if(dp[N] == null) {
			dp[N] = Math.max(recur(N - 1) + arr[N], arr[N]);
 
			// 해당 dp[N]과 max 중 큰 값으로 max 갱신 
			max = Math.max(dp[N], max);
		}
		
		return dp[N];
	}
}

앞서 말했듯 탐색 과정에서 아예 max변수를 두고 해당 index n의 위치에 저장 될 최댓값과 현재 max값을 비교하면서 최댓값을 갱신시키는 것이다. 이렇게 하는 것이 굳이 recur() 탐색 종료 후 또 dp배열을 탐색하면서 최댓값을 찾을 필요 없이 recur() 탐색 과정에서 한 번에 처리할 수 있으니 좀 더 효율적이다.

---

- 방법 2 : [Scanner + Bottom-Up]

import java.util.Scanner;
 
public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		
		int[] arr = new int[N];
		int[] dp = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
 
		/*
		 * dp[0]은 첫 원소로 이전에 더이상 탐색할 것이 없기 때문에
		 * arr[0] 자체 값이 되므로 arr[0]으로 초기화 해준다.
		 * max또한 첫 번째 원소로 초기화 해준다.
		 */
		dp[0] = arr[0];
		int max = arr[0];
		
		for (int i = 1; i < N; i++) {
			// (이전 dp + 현재 arr값) 과 현재 arr값 중 큰 것을 dp에 저장 
			dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
			// 최댓값 갱신 
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);
 
	}
}