[백준] 1219번 연속합 (다이나믹 프로그래밍_JAVA)

티스토리 시작하겠다고 마음먹은 후

미루고 미뤄왔던 알고리즘 정리!

 

사실 엄청난 코드는 아니지만

처음으로 DP문제를 검색 안하고 푼 기념으로 피드 박제

ヾ(≧▽≦*)ヾ

 

 

---

문제 

 

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

1912번: 연속합

 

 

 

---

설계

 

알고리즘 [접근 방법] : DP

숫자가 10만까지 입력받을 수 있는데, 완전탐색으로 접근하면 시간초과 발생할 것이라 생각해 DP로 풀었다.

 

2차원 배열을 만들고, 첫 행은 각 입력값을 저장하고 두번째 행에는 누적합을 저장한다.

중요한 점은 누적합을 저장할 때, 그 전의 열의 두 값을 비교해 더 큰 값과 현재 값을 더한 누적합을 저장한다.

 

본문의 예제를 예를 든다면, 

배열[1][2](=9)의 값은, 그 전의 열의 값 -4와 6을 비교해 더 큰 값(=6)과 입력값(=3)을 더한 값이다.

배열[1][8](=33)의 값은, 그 전의 열의 값 12와 -2를 비교해 더 큰 값(=12)와 입력값(=21)을 더한 값이다. 

 

10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14	-2	33	32

 

이런 식으로 배열을 채워나간 후, 배열을 순회하면서 가장 높은 값을 찾으면 된다.

 

 

 

---

코드

import java.util.Arrays;
import java.util.Scanner;

public class Test_1912_연속합 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//배열 크기 입력받기
		int n = sc.nextInt();
	
		//배열 생성 및 값 입력받기
		int[][] arr = new int[3][n];
		for(int i=0; i<n; i++) {
			arr[0][i]=sc.nextInt();	//현재값
		}
		
		//dp
		int max=0;
		for(int i=0; i<n; i++) {
			arr[1][i]=max+arr[0][i];	//누적합+현재값
			
			max=Math.max(arr[1][i], arr[0][i]);	//누적합, 현재값 비교하기
		}
		
		//최대값 찾기
		int result=Integer.MIN_VALUE;
		for(int i=0; i<n; i++) {
			int tmp=Math.max(arr[0][i], arr[1][i]);
			result=Math.max(tmp, result);
		}
		
		//출력
		System.out.println(result);
	
	}
}

 

 

(❁´◡`❁)

끝!