백준 꿀따기 21758 java

문제링크

문제 접근

• 벌통의 위치는 0 또는 N - 1 이어야 최대
• 벌통 0 일때 벌1은 N-1, 벌2 위치 바꿔가며 최댓값 갱신
• 벌통 N-1 일때 벌1은 0, 벌2 위치 바꿔가며 최댓값 갱신
• 처음 접근에는 양 끝을 제외한 꿀 양이 가장 적은 위치를 이용하여 시도했으나 최댓값 보장 안됨

코드

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

public class baek_21758 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int max = 0;
        long answer = 0;
        int N = Integer.parseInt(st.nextToken());
        int[] map = new int[N];
        long[] left = new long[N];
        long[] right = new long[N];
        long totalSum = 0;
        st = new StringTokenizer(br.readLine());
        int sum = 0;
        for(int i=0;i<N;i++){
            map[i] = Integer.parseInt(st.nextToken());
            if(map[i] > max) max = map[i];
            totalSum += map[i];
            sum += map[i];
            right[i] = sum;
        }
        sum = 0;
        for(int i=N-1;i>=0;i--){
            sum += map[i];
            left[i] = sum;
        }
        if(N == 3){
            System.out.println(max * 2);
            return;
        }
        ////////////벌통 0
        for(int i=1;i<N;i++){
            long bee1 = totalSum - map[0] - map[i];
            long bee2 = totalSum - right[i];
            if(bee1 + bee2 > answer) answer = bee1 + bee2;
        }
        ////////////벌통 N - 1
        for(int i=N-2;i>=0;i--){
            long bee1 = totalSum - map[N-1] - map[i];
            long bee2 = totalSum - left[i];
            if(bee1 + bee2 > answer) answer = bee1 + bee2;
        }


//        /////////////////벌통 0
//        /////case 1 : 통 --------벌,벌
//        for(int i=N-3;i>=0;i--){
//            sum += map[i];
//        }
//        sum *= 2;
//        if(answer < sum) answer = sum;
//        /////case 2 : 통 ---- 가장작은map[i]중 오른쪽 벌 -- 벌
//        sum = 0;
//        for(int i=N-2;i>=0;i--){
//            if(i == minIndex.get(minIndex.size()-1)){
//                isDouble = true;
//                continue;
//            }
//            if(!isDouble) sum += map[i];
//            else if(isDouble){
//                sum += (map[i] * 2);
//            }
//        }
//        if(answer < sum) answer = sum;
//        /////////////////벌통 N - 1
//        /////case 1 : 벌,벌 ------- 통
//        sum = 0;
//        for(int i=2;i<N;i++){
//            sum += map[i];
//        }
//        sum *= 2;
//        if(answer < sum) answer = sum;
//        /////case 2 : 벌 -- 가장작은map[i]중 왼쪽 ----- 통
//        sum = 0;
//        isDouble = false;
//        for(int i=1;i<N;i++){
//            if(i == minIndex.get(0)){
//                isDouble = true;
//                continue;
//            }
//            if(!isDouble) sum += map[i];
//            else if(isDouble){
//                sum += (map[i] * 2);
//            }
//        }
//        if(answer < sum) answer = sum;

        System.out.println(answer);
    }
}

결과

정리

• 처음 접근한 방법에 대해 테스트 케이스 대입해보며 확인했어야 함
• 누적 합을 활용하여 반복 제거