[백준] 1912 - 연속합 (Java)

[백준] 1912 - 연속합 (Java)

문제

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

풀이/후기

DP 문제를 계속해서 풀면서 정말 오랜만에 자력으로 점화식을 도출해냈다.

아주 자신감있게 풀어서 주어진 예제가 모두 맞게 나오는 것을 확인하고 제출하니 오답이 나왔다.

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

이 점화식에선 무조건 두 개 이상의 숫자를 선택한 경우이다.

연속된 몇 개의 수를 선택하는 경우 외에 하나의 수만 선택할 수도 있으므로 arr[i]는 꼭 더해져야 하는 부분이 아니다.

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

이렇게 수정하니 정답처리가 되었다.

정말 오랜만에 자신있게 풀었는데,, 마무리가 뿌듯하지는 않아서 아쉽다.

코드

package DynamicProgramming;

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

public class Problem1912 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str;
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] dp = new int[N];
		
		str = new StringTokenizer(br.readLine());
		
		for (int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(str.nextToken());
		}
		
		dp[0] = arr[0];
		int result = dp[0];
		
		for (int i=1; i<N; i++) {
			dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
			if (result < dp[i]) result = dp[i];
		}
		
		System.out.println(result);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/53c9e95d685ba65ad050330db0df3224d2d756f7

참고