[백준알고리즘-JAVA]1912번 풀이(연속합) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1912번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

입력 예제

10
10 -4 3 1 5 6 -35 12 21 -1

출력 예제

33

입력 예제

10
2 1 -4 3 4 -4 6 5 -5 1

출력 예제

14

입력 예제

5
-1 -2 -3 -4 -5

출력 예제

-1

성공코드

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

public class Main {

	static int[] arr;
	static Integer[] dp;
	static int N;
	static int max = Integer.MIN_VALUE;
	static int temp = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[N];
		dp = new Integer[N];
		
		for(int i = 0 ; st.hasMoreTokens() ; i ++)
			arr[i]=Integer.parseInt(st.nextToken());
		
		dp[0] = arr[0];
		max = arr[0];
		sum(N-1);
		
		System.out.println(max);
}
	public static int sum(int num) {
				
		if(dp[num]==null) {
			dp[num] = Math.max(sum(num-1)+arr[num] , arr[num]);
			
			max = Math.max(max, dp[num]);
		}
		
		return dp[num];
	}

}

연속 합의 문제는 의외로 쉽게 풀릴 수 있는 문제였습니다. 단, 규칙만 파악한다면 이지요... ㅎㅎ

 

STEP을 따라가며 규칙을 파악하여 풀어보도록 하죠

---

알고리즘 흐름도

입력받기 -> DP 초기값 설정 -> 재귀 OR 반복문으로 답 도출 -> 출력하기

---

STEP1 규칙 찾아내기

 규칙을 찾아내려면, 일단 막일로 적어봐야 합니다. 동적 계획법에 맞게 DP에 무엇을 넣을지 먼저 생각해 봅시다. 우리가 찾아야 하는 값은 연속된 값의 합입니다. 그렇다면, dp에는 각 자릿수까지의 최댓값을 찾으면 됩니다. 음 여기서 무조건 기억하셔야 될게 바로 연속적으로 되어야 한다는 겁니다.

 

이 조건을 기억하고 하나씩 채워보도록 하죠

arr	10	-4	3	1	5	6	-35	12	21	-1
dp

arr	10	-4	3	1	5	6	-35	12	21	-1
dp	10

처음은 아주 간단하죠 자기 자신을 넣습니다.

arr	10	-4	3	1	5	6	-35	12	21	-1
dp	10	6

여기서 최대는 -4 아니면 6이 되는데 최고갑승ㄴ 6이죠 이런 식으로 아래 표까지 채워줍니다.

arr	10	-4	3	1	5	6	-35	12	21	-1
dp	10	6	9	10	15	21	-14

이제 바로 여기서 가 핵심!!!

이제 다음에 들어오는 12는 이전의 최댓값인 -14에 자기 자신을 더해주면 -2가 됩니다. 그러나 이전의 연속 합보다 자기 자신의 값이 더 큰 것을 알 수 있죠

 

이에 따라서 이때는 바로 자기 자신을 넣어줍니다.

이런 식으로 요!

 

 

그렇다면 이제 규칙이 잘 보이죠

dp [1] = Math.max(dp [0] + arr [1], arr [1]) 이런 식으로 비교하면서 올라가게 되죠

 

물론 처음에 저도 어떻게 dp를 저렇게 생각하지?라는 의문이 많이 들었습니다.

 

동적 계획 법을 풀어보면서 dp를 어떻게 설정하냐가 저에게는 가장 어려웠습니다.

 

dp를 어떻게 설정할지 안다면, 그냥 막일을 통해 답을 도출하기 쉬워지기 때문이죠

 

 

간략하게 dp를 설정하는 가이드를 조금 제시해보겠습니다.

 - 문제에서 원하는 답이 들어갈 수 있도록 설정한다.

 - 각 인덱스까지의 최댓값 / 최솟값을 구한다.

 - 이를 재귀나 반복을 이용하여 dp를 도출한다.

 - 원하는 결과를 도출한다

 

물론 모든 dp가 이런 식으로 풀리지는 않지만, 어느 정도의 문제는 충분히 가능하다고 생각합니다~1

---

STEP2 DP 초기값 설정

 dp 초기값은 앞서 설명한 대로 바로 자기 자신이 되어야 합니다. 이에 따라 코드를 작성해 주세요

dp[0] = arr[0];

---

STEP 3 재귀 구현하기

public static int sum(int num) {
				
		if(dp[num]==null) {
			dp[num] = Math.max(sum(num-1)+arr[num] , arr[num]);
			
			max = Math.max(max, dp[num]);
		}
		
		return dp[num];
	}

재귀 구현은 한결 간단하죠. 아까 STEP1에서 찾은 규칙을 그대로 넣어줍니다!

 

여기서 바로 max에 비교해서 값을 넣어주셨는데 dp를 다 채우고 나서 main에서 다시 최댓값을 구해도 무관합니다!

 

그러나 이왕 하는 재귀에서 max를 해준다면 불필요한 반복문을 한번 줄일 수 있는 이점이 있죠

 

좀 더 자세히 설명해드리자면,

 

 - if문 : 메모이제이션을 위해서 설정 ( null 이면 재귀를 해라)

 - dp [num] = ~~ : 핵심 문장으로 이전 dp를 비교해서 더 큰 값을 넣어라

 - max : 출력할 정답을 저장하는 변수

---

STEP 4 반복문 구현하기

 이는 재귀 말고 반복문으로 구현한 방법입니다. 뭐 큰 차이는 없습니다.

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

public class Main {

	static int N;
	static int[] arr;
	static int[] dp;
	static int max;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new int[N];
		dp = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		dp[0] = arr[0];
		max = arr[0];
		
		for(int i = 1 ; i < N ; i++) {	
				dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
				max = Math.max(max, dp[i]);
		}	
		System.out.println(max);

		}
}