[BOJ] 1912. 연속합 - JAVA

🔗 문제

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

1912번: 연속합

 

💻 풀이 및 코드

문제 유형 : 다이나믹 프로그래밍

 

요약 : 연속된 구간의 합의 최댓값

 

풀이

DP 를 풀 때 나는 N 개의 숫자가 주어졌을 때 N 번째의 해당하는 답을 구하기 위해서 첫번째만 숫자가 주어졌을 때, 다음 두 번째 숫자가 주어졌을 때, 세번째 숫자가 주어졌을 때의 답을 차례대로 유추한다.

 

예제를 보면 [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] 가 주어졌다.

 

10 이 들어왔을 때

현재까지의 최댓값은 10 이다.

 

-4 가 들어왔을 때

나올 수 있는 경우의 수는 3가지이다.

① -4 부터 시작

② 10 + -4 (이전까지의 최대합 + 현재 값)

③ 10 (현재를 뺀 이전까지의 최대합)

 

-4 보다 6 이 더 크기 때문에 dp[i] 에 6을 저장한다. 이 값은 i 번째까지의 합을 고려했을 때 가장 큰 값을 의미한다.

ans 에는 10 과 6 을 비교해서 10 을 저장한다. 이 값은 현재까지 구한 값 중 최댓값을 의미한다. 

 

3이 들어왔을 때

이 경우도 나올 수 있는 경우의 수는 동일하게 3가지이다.

① 3부터 시작

② 6 + 3 (이전까지의 최대합 + 현재 값)

③ 10 (직전까지 구한 값 중 최댓값)

 

역시 3보다 9가 더 크게 때문에 dp[i] 에 9를 저장한다. 

ans 에는 10과 9를 비교해서 10이 더 크기 때문에 10을 저장한다. 

 

1이 들어왔을 때

위와 동일하다.

① 1부터 시작

② 9 + 1 (이전까지의 합 + 현재 값)

③ 10 (직전까지 구한 값 중 최댓값)

 

dp[i] = 10

ans = 10

 

...

 

차례대로 계속 진행해보면 왜 dp[i] 와 ans 를 따로 하는 지 알 수 있고 점화식을 찾을 수 있다.

 

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

ans = Math.max(dp[i], ans);

 

---

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_1912_연속합 {

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_bj_1912.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int[] dp = new int[N];
		dp[0] = Integer.parseInt(st.nextToken());
		int ans = dp[0];
		
		for(int i=1; i<N; i++) {
			int num = Integer.parseInt(st.nextToken());
			
			dp[i] = Math.max(dp[i-1] + num, num);
			ans = Math.max(ans, dp[i]);
		}
		System.out.println(ans);
		br.close();
	}

}

 

---

Reference

[백준] 1912번 : 연속합 - JAVA [자바]