특별한 마법 공격
면접 대비시간 제한1초메모리 제한1024 MB
인접한 두 학생마다 한 명 이상을 선택하도록 하면서 선택한 학생들의 저항력 합을 최소로 만드는 값을 구한다.
문제
NLCS Jeju에는 화재 경보가 울리면 모든 커플이 헤어진다는 징크스가 있다......
시이(swi)는 하라는 공부는 안 하고 연애만 하는 학생들이 NLCS Jeju에 너무 많은 것을 보고 이들에게 시이-빔을 쏘아 단죄하기로 하였다.
언제나처럼 화재경보기가 오작동해 학생 명이 대피하여 운동장에 한 줄로 서있다. 시이는 커플인 두 사람 중 한 명 이상을 단죄하려고 한다. 하지만 이들 중 누가 커플인지 모르기 때문에 시이는 다음 규칙에 따라 학생들을 단죄하기로 하였다.
- 모든 서로 인접한 두 학생 중 한 명 이상을 단죄해야 한다.
하지만 각 학생은 시이-빔에 대한 저항력이 있어 앞에서 번째 학생을 시이-빔으로 단죄하기 위해서는 만큼의 에너지가 필요하다.
시이가 규칙을 만족하도록 학생들을 단죄하기 위해 필요한 총 에너지의 최솟값을 구하여라.
입력
첫 번째 줄에 학생의 수를 나타내는 정수 이 주어진다.
두 번째 줄에 각 학생의 저항력을 나타내는 개의 정수 이 공백으로 구분되어 주어진다.
출력
시이가 규칙을 만족하도록 학생들을 단죄하기 위해 필요한 총 에너지의 최솟값을 정수로 출력한다.