백준 1912번: 연속합

문제

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

1912번: 연속합

---

풀이

n개의 정수로 이루어진 수열 중에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

dp 배열은 임의의 수 x가 있을 때 arr[x]가 맨 오른쪽에 있을 때 연속된 몇 개의 수의 합 중 가장 큰 값을 의미합니다.

continous 함수 안에서 dp[idx]가 null이라면 coninous(idx - 1)를 재귀적으로 실행하여 dp[idx - 1]를 받아 그 값에 arr[idx]값을 더한 값과 아무것도 더하지 않은 arr[idx]값을 비교해서 더 큰 값을 넣습니다.

이후 max값과 dp[idx]값을 비교해가며 최댓값을 구하기 때문에 모든 입력이 끝난 후에 continous(n - 1)을 실행하여 dp[n - 1부터 0]을 모두 비교한 뒤에 max를 출력합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int max = Integer.MIN_VALUE;
    static int[] arr;
    static Integer[] dp;

    public static int continous(int idx) {
        if (dp[idx] == null) {
            dp[idx] = Math.max(continous(idx - 1) + arr[idx], arr[idx]);
        }
        max = Math.max(max, dp[idx]);
        return dp[idx];
    }

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

C언어

바텀업 방식을 이용한 코드입니다.

dp 배열은 탑다운 방식의 코드에서의 의미와 동일하며 모든 입력이 끝나면 i를 포함한 for문으로 들어가게 되는데 이때 i가 1부터 시작하기 때문에 max에는 arr[0]값을 넣어줍니다.

이후 for문 안에서 dp[i - 1]값에 arr[i]값을 더한 값과 아무것도 더하지 않은 arr[i]값을 비교해서 더 큰 값을 넣고 max와 dp[i]값을 비교해가며 최댓값을 구한 뒤에 for문이 끝나면 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define math_max(a, b) a > b ? a : b
main() {
	int n;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	int* dp = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	int max = dp[0] = arr[0];
	for (int i = 1; i < n; i++) {
		dp[i] = math_max(dp[i - 1] + arr[i], arr[i]);
		max = math_max(max, dp[i]);
	}
	printf("%d", max);
}

 

---

결론

자바로 탑다운 방식을 이용한 코드에서 continous 함수를 1번만 실행해서 모든 dp 배열의 값을 비교한 후에 max를 구할 수 있다는 다이나믹 프로그래밍이 필요하지 않다는 뜻과 같다고 느껴져서 조금 찝찝한 풀이였습니다.