[SW Expert Academy/Java/D3] 5642.합

1) SW Expert Academy 정책상 문제 자체를 퍼가는 것은 금지되며 링크와 출처로 명시해 주시기 바랍니다.
2) 문제에 대한 본인의 풀이에 대해서는 개인 학습 등 상업적 용도가 아닌 경우에만 문제 출처와 함께 게시가 가능합니다.
    
※ 저작권 이슈가 있을 시 법적 제재를 받을 수 있으니 참고하여주시기 바랍니다.

 

문제 설명

SW Expert Academy

 

나의 풀이

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 테스트케이스 개수

        for (int tc = 1; tc <= T; tc++) {
            int N = scanner.nextInt(); // 배열의 크기
            int[] arr = new int[N];

            for (int i = 0; i < N; i++) {
                arr[i] = scanner.nextInt(); // 배열 요소 입력받기
            }
			
            // 카데인 알고리즘 적용
            int currentSum = arr[0]; // 현재 연속 부분 합
            int maxSum = arr[0]; // 최대 연속 부분 합

            for (int i = 1; i < N; i++) {
                currentSum = Math.max(arr[i], currentSum + arr[i]); // 현재 위치에서의 최대합 계산
                maxSum = Math.max(maxSum, currentSum); // 최대 합 갱신
            }

            System.out.println("#" + tc + " " + maxSum); // 결과 출력
        }

        scanner.close();
    }
}

이 문제는 연속된 부분 수열 중 합이 가장 큰 값을 찾는 문제이다. 

목표: 주어진 정수 배열에서 연속된 요소의 합 중 최대값을 찾는다.
조건: 연속된 정수로 부분 수열을 만들 수 있지만, 그중 가장 합이 큰 부분 수열을 찾아야 한다.

예를 들어 [1, 3, -8, 18, -8]라는 배열이 주어지면, 부분 수열 중 합이 가장 큰 조합을 찾아야 한다. 이때, 18 하나만 선택하면 합이 최대 18이 된다. 또 다른 예로는 [1, -2, 3, 4, -1, 2] 배열에서는 [3, 4, -1, 2]라는 연속 구간을 선택하면 최대합이 된다.

이 문제는 ‘카데인 알고리즘’을 사용하여 해결할 수 있다. 이 알고리즘은 연속된 부분 수열의 최대합을 효율적으로 구하는 방법이다.

* 카데인 알고리즘은 다이나믹 프로그래밍(동적 계획법)을 적용한 방식

<카데인 알고리즘 개념>
1.배열을 순회하며 각 위치에서 “이전까지의 최대 연속 합”과 현재 위치의 값을 더해 현재 위치에서 끝나는 부분 수열의 최대 합을 구한다.
2.만약 현재 위치의 값만 포함한 합이 더 크다면, 새로운 부분 수열을 시작한다.
3.모든 위치에서 최대 합을 비교해 전체의 최대값을 구한다.

<풀이 절차>
1.변수 정의
-current_sum: 현재 위치에서 끝나는 부분 수열의 최대 합
-max_sum: 전체 수열 중 가장 큰 부분 수열의 합
2.배열의 첫 번째 요소부터 시작하여 각 요소를 순회하며 위의 값을 업데이트한다.
3.각 요소에서 current_sum이 max_sum보다 크면 max_sum을 갱신한다.

 

다른 풀이

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int tc=1; tc<=T; tc++) {
            int N = sc.nextInt();
            int[] a = new int[N];

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

            int max=-9999, sum = 0;

            for(int i=0; i<N; i++) {
                sum += a[i];
                if( sum > max ) max = sum;
                if( sum < 0 ) sum = 0;
            }

            System.out.format("#%d %d\n", tc, max);
        }
    }
}