iktk   2년 전

문제

당신은 성냥을 가지고 놀고 있습니다. 성냥은 선분 모양이며 둥근 쪽 끝이 머리입니다. 당신은 성냥을 일직선으로 나란히 배열했습니다. 즉, 각 성냥의 한 쪽 끝은 배열의 양 끝을 제외하고는 정확히 하나의 다른 성냥의 한 쪽 끝과 인접해 있습니다.

preview

성냥 배열의 예시

당신은 라이터를 이용해 가장 왼쪽 성냥에 불을 붙여서 모든 성냥을 태우고 싶습니다. 인접한 성냥에 불이 옮겨 붙으려면, 인접한 두 성냥 중 적어도 한 개는 머리가 인접해 있어야 합니다. 최소 몇 개의 성냥을 뒤집어야 할까요?

입력

표준 입력의 첫 번째 줄에는 성냥의 개수를 나타내는 하나의 정수 $n$($1 ≤ n ≤ 1\,000\,000$)가 주어집니다. 두 번째 줄은 성냥이 어떻게 놓여져 있는지를 나타내는데, $n$개의 정수 $x_1, x_2, \dots , x_n$이 공백으로 구분되어 주어집니다. 여기서 $x_i$는 $i$번째 성냥의 머리가 왼쪽에 있으면 $0$, 오른쪽에 있으면 $1$입니다.

출력

방향을 뒤집어야 하는 성냥의 최소 개수를 정수로 출력합니다.

힌트

preview

댓글을 작성하려면 로그인해야 합니다.