[소프티어] 효도 음식 (JAVA 풀이)

1. 문제

소프티어 LV3 효도음식 문제를 자바로 풀어보았습니다!!

https://softeer.ai/practice/7367

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

2. 문제 해결 방법

        // 왼쪽에서 오른쪽으로의 최대 합 계산
        int leftSum = nums[0];
        leftMax[0] = leftSum;
        for (int i = 1; i < n; i++) {
            leftSum = Math.max(nums[i], leftSum + nums[i]);
            leftMax[i] = Math.max(leftMax[i-1], leftSum);
        }

        // 오른쪽에서 왼쪽으로의 최대 합 계산
        int rightSum = nums[n-1];
        rightMax[n-1] = rightSum;
        for (int i = n-2; i >= 0; i--) {
            rightSum = Math.max(nums[i], rightSum + nums[i]);
            rightMax[i] = Math.max(rightMax[i+1], rightSum);
        }

예제에서 나와 있는 4 -6 1 2 -1 3 이라는 예시를 통해 설명해보자면, 재료들이 주어졌을 때 왼쪽에서 오른쪽으로의 최대 합과 오른쪽에서 왼쪽으로의 최대 합을 계산해줍니다.

해당 과정을 거치고 나면 아래와 같은 배열 상태가 됩니다.

 

leftMax 배열

4

4

4

4

4

4

leftMax는 i 까지의 부분 배열에서 가능한 최대 연속 부분합을 저장합니다.

각 단계에서 현재 요소를 포함할 것인가 or 새로운 부분 배열을 시작할 것인가를 결정합니다.

 

 

rightMax 배열

4

4

4

3

3

3

rightMax 또한 배열 끝에서부터 시작해 부분 배열에서 가능한 최대 연속 부분합을 저장합니다.

 

 

두 음식의 구간은 인접하면 안되기 떄문에

maxSum = Math.max(maxSum, leftMax[i-1] + rightMax[i+1]);

i 를 기준으로 왼쪽음식의 최대값, 오른쪽 음식의 최댓값을 더해 최대 만족도를 찾아줍니다.

 

 

3. 전체 코드

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[] nums = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int result = maxSumTwoFoods(nums);
        System.out.println(result);
    }

    public static int maxSumTwoFoods(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        // 왼쪽에서 오른쪽으로의 최대 합 계산
        int leftSum = nums[0];
        leftMax[0] = leftSum;
        for (int i = 1; i < n; i++) {
            leftSum = Math.max(nums[i], leftSum + nums[i]);
            leftMax[i] = Math.max(leftMax[i-1], leftSum);
        }

        // 오른쪽에서 왼쪽으로의 최대 합 계산
        int rightSum = nums[n-1];
        rightMax[n-1] = rightSum;
        for (int i = n-2; i >= 0; i--) {
            rightSum = Math.max(nums[i], rightSum + nums[i]);
            rightMax[i] = Math.max(rightMax[i+1], rightSum);
        }

        // 두 음식의 최대 합 계산
        int maxSum = Integer.MIN_VALUE;
        for (int i = 1; i < n-1; i++) {
            maxSum = Math.max(maxSum, leftMax[i-1] + rightMax[i+1]);
        }
        return maxSum;
    }
}