백준 - 18228번(펭귄추락대책위원회)

문제 출처: https://www.acmicpc.net/problem/18228

문제

• 일우는 친구들과 펭귄 얼음깨기 게임을 하고 있다. 계속 떨어지는 펭귄이 불쌍했던 일우는 INU 송년 코드페스티벌 참가자들을 펭귄추락대책위원회로 초대했다. 이 펭귄 얼음깨기는 리메이크 된 버전으로, N개의 얼음이 1부터 N까지 번호가 매겨져 있다. 게임은 얼음 1부터 N까지 순서대로 일렬로 나열된 공간에서 진행된다. 게임 시작 시, 펭귄 한 마리가 임의의 얼음 K위에 위치한다. 참가자는 몇 개의 얼음을 깨뜨려서 펭귄을 떨어뜨리는 것이 목적이다. 단, 펭귄이 밟고 있는 얼음은 깨뜨릴 수 없다. 각 얼음은 서로 다른 강도를 가지고 있어서 얼음 i(1 ≤ i ≤ N)를 깨뜨리는 데에 Ai만큼의 힘이 필요하다. 양옆으로 인접해 있는 얼음들을 하나의 그룹으로 봤을 때, 그룹의 끝이 얼음1 또는 N을 포함하지 않는다면 이 얼음 그룹은 아래로 추락하게 된다. 아래 예시를 보자.
  얼음4와 얼음1을 각각 2와 7의 힘을 가해 깨뜨릴 수 있다. 이때, 펭귄이 위치한 얼음2와 얼음3으로 구성된 그룹은 얼음1 또는 얼음5를 포함하지 않으므로 아래로 추락하게 된다. 위 예시에서 펭귄을 떨어뜨릴 수 있는 최소 힘은 2+7=9가 된다.
  
  펭귄추락대책위원회인 우리는 게임의 참가자가 펭귄을 떨어뜨릴 수 있는 최소 힘을 구해서 이를 보완하려고 한다. 펭귄을 떨어뜨릴 수 있는 최소 힘은 얼마일까?

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(reader.readLine());
        int[] nums = new int[size];
        String[] temp = reader.readLine().split(" ");
        int penguin = -1;
        int min = Integer.MAX_VALUE;
        int result = 0;
        for (int i = 0; i < size; i++) {
            nums[i] = Integer.parseInt(temp[i]);
            if (nums[i] == -1) {
                penguin = i;
            }
        }
        // 펭귄 위치 좌, 우로 가장 작은 값 2개를 더함
        for (int i = 0; i < size; i++) {
            if (i == penguin) {
                result += min;
                min = Integer.MAX_VALUE;
                continue;
            }

            if (nums[i] < min) {
                min = nums[i];
            }
        }
        result += min;

        System.out.println(result);
    }

}

• 초기 접근시 엉뚱하게 그룹 얼음도 깰 수 없다고 생각하여 1회차를 실패하였다.
• 펭귄의 위치를 기준으로 왼쪽에서 가장 작은 수와 오른쪽에서 가장 작은 수를 구하여 더하면 되는 간단한 문제.