[백준-1912번 자바/java] 연속합 _디버깅의 눈물

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

1912번: 연속합

 

 

 

연속합 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

128 MB

109463

38778

27231

34.145%

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

33

예제 입력 2 복사

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

예제 출력 2 복사

14

예제 입력 3 복사

5
-1 -2 -3 -4 -5

예제 출력 3 복사

-1

 

 

 

 

---

 

 

체크 포인트

 

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법) 이용

-큰 문제를 작은 경우부터 탐색해 추론해나가는 dp를 이용해 풀이를 시도했다.

-결과적으로 간단한 문제였지만, 처음에 문제의 조건인 '연속된 몇개의 수를 선택해 구할 수 있는 합의 최대합'을 이해하는데 시간이 다소 소요되었다.

 

-예제 1번을 예로 추론과정을 적어보자면,

 

n	0	1	2	3	4	5	6	7	8	9	10
arr[i]	0	10	-4	3	1	5	6	-35	12	21	-1
dp[i]	0	10	6 (10-4)	9 (6+3)	10 (9+1)	15 (10+5)	21 (15+6)	-14 (21-35)	12	33 (12+21)	33

 

1) int 배열 arr을 0부터 10번까지 선언하고 값을 입력 받는다.

2)연속된 수 합의 최대합을 의미하는 dp배열의 추론을 시작한다.

 

dp[1]일 때 연속된 수의 최대합은 10 하나이므로 10이다.

dp[2]일 때 연속된 수의 최대합은 (1)10+(-4)와 (2)-4가 존재한다. 최대합은 이중 더 큰값인 (1)10+(-4)이다.

dp[3]일 때 연속된 수의 최대합은 (1)6+3과 (2)3이 존재한다. 최대합은 이중 더 큰값인 (1)6+3이다.

dp[4]일 때 연속된 수의 최대합은 (1)9+1과 (2)1이 존재한다. 최대합은 이중 더 큰값인 (1)9+1이다.

dp[5]일 때 연속된 수의 최대합은 (1)10+5와 (2)5가 존재한다. 최대합은 이중 더 큰값인 (1)10+5이다.

dp[6]일 때 연속된 수의 최대합은 (1)15+6과 (2)6이 존재한다. 최대합은 이중 더 큰값인 (1)15+6이다.

dp[7]일 때 연속된 수의 최대합은 (1)21+(-35)와 (2)-35가 존재한다. 최대합은 이중 더 큰값인 (1)21+(-35)이다.

dp[8]일 때 연속된 수의 최대합은 (1)-14+12와 (2)12가 존재한다. 최대합은 이중 더 큰값인 (2)12이다.

dp[9]일 때 연속된 수의 최대합은 (1)12+21와 (2)21이 존재한다. 최대합은 이중 더 큰값인 (1)12+21이다.

dp[10]일 때 연속된 수의 최대합은 (1)33과 (2)33+(-1)이 존재한다. 최대합은 이중 더 큰값인 (1)33이다.

 

위의 추론 과정을 통해 정답은 33임을 알 수 있다.

 

dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);

 

이를 식으로 표현하면 위와 같이 표현할 수 있다.

 

 

 

 

 

풀이

 

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

public  class Main {
	
	// 초기에 주어진 숫자를 담는 배열
	static int[] arr;
	
	// 연속된 최대의 합을 담는 dp 배열
	static int[] dp;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	// n개의 정수
    	int n = Integer.parseInt(st.nextToken());
    	
    	// 배열 초기화
    	arr = new int[n+1];
    	dp = new int[n+1];
    	// 0번째 값 초기화
    	dp[0] = arr[0] = 0;
    	
    	st = new StringTokenizer(br.readLine()," ");
    	
    	// 주어진 숫자 입력
    	for(int i=1; i<=n; i++){
    		arr[i] =Integer.parseInt(st.nextToken()); 
    	}
    	
    	// 탐색 시작
    	solution(n);
    	
    	
    } // end of Main
    
    
    static void solution(int n) {
    	// 연속된 숫자들의 최대합을 담는 변수
    	int max = Integer.MIN_VALUE;
    
    	// bottom-up 방식
    	for(int i=1; i<=n; i++){
    		// dp[i]는 
    		// 1) (i-1)번째까지 연속된 최대합 + 현재 숫자
    		// 2) 현재 숫자
    		// 중에서 더 큰 수로 입력
    		dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
    		
    		// i번째까지 연속된 숫자들의 최대합이 기존 max보다 크다면,
    		if(dp[i]>max){
    			// 최대값 변경
    			max = dp[i];
    		}
    	}
    	
    	System.out.println(max);
    	
    } // end of solution
    
} // end of Main