[백준, 자바, S2] 연속합

0. 문제 링크

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

1912번: 연속합

---

1. 문제 핵심

1. 연속된 숫자들의 합 중 가장 큰 수를 더하는 것

---

2. 문제 접근

1. DP 문제인 것을 알고 있었던만큼 이전의 값으로 이후의 결과를 도출하기 위한 아이디어를 생각했었다.
2. 첫 값은 먼저 받아서 변수들에 입력해준 뒤 이후에 입력 받은 값들을 더했을 때 case에 따라 나눠 구분했다.
3. 합이 0보다 작아지는 경우 sum을 가장 마지막에 입력받은 값으로 바꿔주었고 sum이 양수인 경우엔 새 값을 추가해주었다.
4. 이렇게 sum에 처리를 해준 것을 기존의 answer와 비교해서 항상 더 큰 값을 answer에 새로 저장하게 했다.

---

3. 코드 분석

 

---

4. 베스트 코드 분석

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    int N;
    int[] dt;
    int[] dp;

    public void solve() throws IOException {
        int N = sc.nextInt();
        dt = new int[N];

        for(int i=0; i<N; ++i) {
            dt[i] = sc.nextInt();
        }

        dp = new int[N+1];

        int r = Integer.MIN_VALUE;

        for(int i=1;i<N+1; ++i) {
            dp[i] = Math.max(dt[i-1], dt[i-1]+dp[i-1]);
            r = Math.max(r, dp[i]);
        }

        println(r);
    }

데이터를 입력받은 배열과 해당 배열로 값을 계산한 dp 배열을 두개 선언해주었다.

이 코드가 더 DP적인 것처럼 느껴졌는데 전에 사용된 데이터가 무엇인지 명확히 알 수 있었기 때문이다.

---

5. 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int arr[] = new int[N];
		int sum = 0, tmp = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr[0] = Integer.parseInt(st.nextToken());
		int answer = sum = arr[0];

		for (int i = 1; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			// 기존의 합이 0보다 작은 경우 새로 받는 값을 sum에 저장
			if (sum < 0) {
				sum = arr[i];
			}
			// 기존의 합이 0보다 큰 경우 새로 받는 값을 sum에 합침
			else {
				sum += arr[i];

			}
			answer = Math.max(answer, sum);
			// 더했더니 양수지만 커지는 경우
		}
		System.out.println(answer);
	}
}