백준 1912 - 연속합 JAVA

문제, 입출력, 테스트케이스

제출 내역

해당 문제는 손으로 끄적여가면서 풀다가 탁 깨달은 시점에서 술술 풀어나간 문제이다. 생각보다 매우 간단한 로직이지만 그동안 풀었던 문제들 + 단계별로 풀기 끝에 있다는 것을 감안해서 스스로 어려운 문제일 것이다라고 되뇌다가 시간이 오래 걸린 문제이다. -> "생각보다 쉬웠다"라는 뜻

 

<문제 접근/풀이과정>
1. n개의 정수, 1 <= n <= 100,000, -1,000 <= 각 원소의 크기 < 1,000
-> maxTotal =  100,000,000, minTotal = -100,000,000
-> 그렇다면? int배열 선언

2. 숫자를 쭉 더해가다가 갑자기 연속합(누적합)이 0보다 낮아지는 시점이 생기면 그때는 굳이 합하지 않는 것이 최선이지 않을까? 말짱 도루묵인 시점이니까!
ex)  1 2 -1000 -> 1 + 2 가 최대고 -1,000일 때는 굳이 안 더해주는 게 나을지도?

3. 그렇다면 합한 수가 0보다 낮아지지 않는 시점까지는 연속합(누적합)을 해주다가 0보다 낮은 경우에는 그냥 연속합(누적합)에 넣는 것을 포기하고 다시 0보다 큰 수가 나오는 시점부터 합해주면 좋을 듯 하다.

4. 동시에 max값은 유지하면서 n번 째까지 다 돌았을 때의 max값이 답일 것이다.

일반적으로 입력을 받을 때 로직을 처리하는 것을 별로 좋아하지 않는다. 본인 실력이 매우 뛰어난 수준이 아니라 추후 디버깅 단계에서 꼬일 수도 있기 때문이다.

하지만 이번만큼은 굳이 입력과 처리 로직을 분리하지 않아도 괜찮겠다는 생각에 입력+처리 로직을 동시에 구현해 보았다.

package boj;

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

public class Boj_1912 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 연속된 수의 합
		// 10	-4	3	1	5	6	-35	12	21	-1
		// 10	6	9	10	15	21	X	12	33	33
		// 10	10	10	10	15	21		21	33	33
		
		// 2	1	-4	3	4	-4	6	5	-5	1
		// 2	3	X	3	7	3	9	14	9	10
		// 2	3	3	3	7	7	9	14	14	14
		
		// -1	-2	-3	-4	-5
		// -1	-1	-1	-1	-1
		
		// 1. 1번 부터 i번까지 더했다 
        //=> dp에 max값 갱신하면서 이제 더한 수가 0일 때는 커서를 
        // 그다음의 양수값으로 옮김 그때까지는 dp배열에 최댓값을 넣는다.
		// 2. 1 <= n <= 100,000 / -1,000 <= ni < 1,000 
        // total 최대 100,000,000 / 최소 -100,000,000 -> int 배열 선언
		// 3. 100,000 -> BR, STZ
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		int n = Integer.parseInt(br.readLine());
		int arr[][] = new int[n+1][2];
		stz = new StringTokenizer(br.readLine());
		int max = -1001;
		int Lcursor = -1;
		int Rcursor = -1;
		for (int i = 1; i <= n; i++) {
			arr[i][0] = Integer.parseInt(stz.nextToken());
			
			if(arr[i][0] + arr[i-1][1] > 0) {
				arr[i][1] = arr[i][0] + arr[i-1][1];
				max = Math.max(max, arr[i][1]);
				if(Lcursor == -1 && Rcursor == -1) { // 이전 값에서 누적합 하지 않은 경우
					Lcursor = i; // 커서 시작
					Rcursor = i;		
				}
				Rcursor = i;
			}else { // 누적합 안하는 경우 -> 초기화
				arr[i][1] = 0;
				Lcursor = -1;
				Rcursor = -1;
				max = Math.max(max, arr[i][0]);
			}
		}
		System.out.println(max);
		
	}
}

문제를 풀 때 간혹가다가 스스로 어렵게 풀려고하는 경향이 있을 때 생각 보다 이 문제는 쉬울 거야라고 되뇌어 보도록 해 보자!