[백준] 1912.연속합 (실버2, Java)

문제

이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. (1개 이상 선택)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

 

풀이

1차 시도: 시간 초과

n의 최대값이 100,000인데 2중 for문이라 시간초과가 발생하는 것 같다.

Dynamic Programming 문제인데 이를 제대로 사용하지 못했다.

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }

    int max = arr[0];
    for (int i = 0; i < n; i++) {
        int temp = arr[i];
        for (int j = i + 1; j < n; j++) {
            max = temp > max ? temp : max;
            temp += arr[j];
        }
    }

    System.out.println(max);
}

 

2차 시도: 성공

반복문을 하나 줄이기위해 여러 블로그를 찾아봤다. 가장 적절했던 풀이를 바탕으로 코드는 보지 않고 구현해봤다.

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

 

maxarr 배열에 연속합의 값을 저장한다.

1개 이상이 연속이라고 했음으로 0번째에는 그냥 대입한다.

그 다음부터 maxarr[0] + arr[1] = 6으로 기존 -4보다 커졌기에 maxarr[1]에 6를 저장한다.

이렇게 가다가 maxarr[6] + arr[7] = -2로 기존12보다 값이 작다. 그래서 이번엔 maxarr[7]에 12를 저장한다.

그 이후 maxarr에서 가장 큰값을 출력하면 된다!

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] maxarr = new int[n];
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }
    maxarr[0] = arr[0];

    for (int i = 1; i < n; i++) {
        maxarr[i] = arr[i] + (maxarr[i - 1] + arr[i] < arr[i] ? 0 : maxarr[i - 1]);
    }

    Arrays.sort(maxarr);
    System.out.println(maxarr[n - 1]);

}

 

 

최종 코드 (시도3)

시도2에서 성공하고 굳이 배열 2개일 필요가 있나?라는 의문이 들었다.

그래서 arr 배열 1개만 사용해서 구현해봤다.

arr[i]가 더 크면 유지하고 그렇지 않을 경우에 arr[i-1]를 더했다.

 

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }

    for (int i = 1; i < n; i++) {
        arr[i] += (arr[i - 1] + arr[i] < arr[i] ? 0 : arr[i - 1]);
    }

    Arrays.sort(arr);
    System.out.println(arr[n - 1]);
}

 

 

 

백준 문제

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