백준 - 1912 연속합 [DP]

 

1912번: 연속합

 

1. 간단 요약

해당 문제는 수열이 주어지면, 해당 수열의 부분연속수열의 합중 가장 큰 값을 구하는 문제이다.

 

2. 접근 방법

• 순차적으로 값을 더한다.
• 다음에 올 숫자가 이득인지 손해인지를 판단한다.
  • 현재까지의 값 + 수열의 현재 인덱스의 값 vs 수열의 현재 인덱스의 값을 비교하여 더 큰 값을 취한다.

 

예를 들어 아래와 같은 수가 주어질 경우

 

-4는 음수이지만 10과 합하면 6이다.

해당 값과 3을 더하면 9이므로, 3보다 크기때문에 손해가 아니므로 취한다.

 

아래처럼 21과 -35를 합하면 -14가 된다.

-14와 12를 더하면 -2이므로 12보다 작다. 손해이므로 버리고 12부터 새로 출발한다.

 

이를 반복한다.

 

모두 반복했을 경우, 33이 가장 큰값이 된다.

 

3. 파이썬

n = int(input())
arr = list(map(int, input().split()))

dp = [0 for _ in range(n + 1)]

for i in range(n):
    dp[i + 1] = max(dp[i] + arr[i], arr[i])

print(max(dp[1:]))

 

4. 자바

아래는 dp 배열을 생성하는 대신 현재 값을 저장하는 방식으로 해주었다.

조건에서 -1000이 가장 작은 값이라 명시되어 있으므로 -1000으로 초기화해주었다.

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());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int now = -1000;
        int max = -1000;
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            now = Math.max(now + num, num);
            max = Math.max(max, now);
        }
        System.out.println(max);
    }
}

 

5. 깃허브 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/1912.%E2%80%85%EC%97%B0%EC%86%8D%ED%95%A9