[JAVA] BOJ(백준) - 연속합 - 1912번 자바

문제내용

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

1912번: 연속합

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

 

---

문제 접근 방법

문제 자체는 몇개의 수를 더하든 연속하는 수를 더했을때 최대가 나오게하면 된다.

이 문제를 풀기위해 DP를 어떻게 활용할까 생각했고 첫번째로 생각한 것은 수열이 주어졌을때

연속되는 수가 1개일때, 2개일때 .... n개일때 까지 계산하여 dp 저장 시킨후 최댓값을 찾는 방법이였다.

예를들어 연속되는 수가 3개일때는 2개일때 계산해놨던 dp를 이용하는 식으로 코드를 작성했는데 우선 dp배열이 2차원배열이 되면서 답은 나오지만 메모리 초과되는 코드가 됐다.

 

메모리 초과가 안나오기 위해선 dp를 1차원배열로 사용해야 했는데 구글링해보니 1차원배열로 훨씬 간단하게 풀수 있는 방법이 있었다. 방법을 보자면

 

'dp[몇번째 인덱스] = 연속합의 최대' 로 정의한다. 이게 무슨 말이냐면 주어진 수열을 이용해

가장처음부터 시작해서 차근차근 수열의 값을 더해 나간다. 그리고 더하면서 현재값과 더한값을 비교하고 더큰 최댓값으로 계속 갱신시켜 주는것이다.

점화식으로 설명하면 dp[i] = Math.max(dp[i-1]+arr[i], arr[i]) 가된다.

문제에서 나온 예시를 활용해 dp값을 계산해 보면 아래표와 같이 나온다.

i	0	1	2	3	4	5	6	7	8	9
arr[i]	2	1	-4	3	4	-4	6	5	-5	1
dp[i]	2	3	-1	3	7	3	9	14	9	10

이때는 최댓값이 7번째 인덱스에서 최댓값이 된다.

즉, 수를 더하다가 더큰 단일값이 나온다면 연속된 그수는 최댓값이 될수가 없기때문에 갱신시켜주는 방식이다.

 

아래 풀이를 보고 생각해보자.

 

---

풀이

BottomUp

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

public class Main {
	static Integer[] dp; // dp[몇번째인덱스] = 최대 연속합
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine());
		dp = new Integer[n];
		arr = new int[n];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		//최댓값변수, 연속합이 1개 일수도 있을때
		//첫번째 값부터 비교하기 위해 초기화
		int max = arr[0];
		//초기화. 입력받은 값이 한개면 dp의 최댓값은 arr[0]일 수밖에 없음.
		dp[0]=arr[0];
		
		
		for(int i=1; i<n; i++) {
			//i-1번째 까지 더한값(dp)+현재 값과 현재값 하나를 비교.
			//만약 현재값(arr) 하나가 더 크다면 연속합일때 최대합이 안됨.
			//그래서 갱신시켜줘야됨.
			dp[i]=Math.max(dp[i-1]+arr[i], arr[i]);
			max = Math.max(max, dp[i]);
			System.out.println(i+" "+dp[i]);
		}
		
		System.out.println(max);
	}
}

 

 

TopDown

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

public class Main {
	static Integer[] dp; // dp[몇번째인덱스] = 최대 연속합
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine());
		dp = new Integer[n];
		arr = new int[n];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		//최댓값변수, 연속합이 1개 일수도 있을때
		//첫번째 값부터 비교하기 위해 초기화
		int max = arr[0];
		//초기화. 입력받은 값이 한개면 dp의 최댓값은 arr[0]일 수밖에 없음.
		dp[0]=arr[0];
		
		//i번째 인덱스일때 최댓값을 하나씩 구하고 비교
		for(int i=1; i<n; i++) {
			max = Math.max(max, sumNum(i));
		}
		
		
		System.out.println(max);
	}
	
	public static int sumNum(int i) {
		if(i<0) {
			return 0;
		}
		if(dp[i]==null) {
			dp[i] = Math.max(sumNum(i-1)+arr[i], arr[i]);
		}
		return dp[i];
	}
}

---

마치며

처음에는 'dp[연속되는수의 개수][몇번째 인덱스] = 각인덱스까지 마다 수의 합' 을 활용해 풀었는데 생각보다 훨씬 쉬운방법으로 풀수 있다는걸 깨닳고 현타온 문제였다,..