[알고리즘 - 백준] 1912번 연속합 (java)

백준 1912번 링크

이번 문제는 전형적인 다이나믹 프로그래밍의 기본문제를 가져와봤다. 내가 문제를 푼 방식과 이 문제의 정답이 약간 다른 부분이 있어서 기억하고 짚어가고자 작성하였다.

내가 푼 방식

1. for문
   (1) dp[i-1]+arr[i]<0 이라면 dp[i] = 0으로 초기화하고(+ boolean 으로 true초기화), 그렇지 않다면 dp[i] = dp[i-1]+arr[i]로 초기화한다. maxSum으로 dp[i]값과 비교하며 최댓값을 갱신해준다.
   (2) 이걸 인덱스 n-1번까지 반복해서 dp배열을 초기화해준다.

2. 만약 maxSum = 0이라면
   (1) 연속된 합의 최댓값이 0일 수도 있고(boolean값이 false)
   (2) for문의 (1)번으로 인해 dp[i]가 0으로 초기화되어 최댓값이 0인 것일 수 있다.(boolean값이 true)
   (3) 따라서 boolean으로 true값이라면 for문을 돌면서 최댓값을 다시 구해준다.

내가 작성한 코드

import java.util.*;
import java.io.*;
class Solution{
	static long dp[], maxSum;
	static int arr[];
	static boolean hasNotAtall;
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		dp = new long[n];
		arr = new int[n];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0] = arr[0];
		maxSum = dp[0];
		for(int i=1;i<n;i++) {
			if(dp[i-1]+arr[i]<0) {
				hasNotAtall = true;
				dp[i] = 0;
			}else {
				dp[i] = dp[i-1]+arr[i];
			}
			
			maxSum = Math.max(maxSum, dp[i]);
		}
		
		if(maxSum == 0 && hasNotAtall == true) {
			maxSum = dp[0];
			for(int i=1;i<n;i++) {
				maxSum = Math.max(maxSum, arr[i]);
			}
		}
	
		
		System.out.println(maxSum);
		
	}
	
}

정석으로 푸는 방법

1. 인덱스 1부터 n-1까지 반복하면서 dp[i-1]+arr[i]와 arr[i]값을 비교해서 이 중 최댓값을 dp[i]에 초기화해준다.
2. 인덱스마다 1번을 하면서 maxSum의 최댓값을 dp[i]와 비교하면서 maxSum의 최댓값 갱신을 해준다.

import java.util.*;
import java.io.*;
class Solution{
	static long dp[], maxSum;
	static int arr[];
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		dp = new long[n];
		arr = new int[n];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[0] = arr[0];
		maxSum = dp[0];
		for(int i=1;i<n;i++) {
			dp[i] = Math.max(dp[i-1]+arr[i], arr[i]);
			maxSum = Math.max(maxSum, dp[i]);
		}
	
		
		System.out.println(maxSum);
		
	}
	
}