당신은 성냥을 가지고 놀고 있습니다. 성냥은 선분 모양이며 둥근 쪽 끝이 머리입니다. 당신은 성냥을 일직선으로 나란히 배열했습니다. 즉, 각 성냥의 한 쪽 끝은 배열의 양 끝을 제외하고는 정확히 하나의 다른 성냥의 한 쪽 끝과 인접해 있습니다.
성냥 배열의 예시
당신은 라이터를 이용해 가장 왼쪽 성냥에 불을 붙여서 모든 성냥을 태우고 싶습니다. 인접한 성냥에 불이 옮겨 붙으려면, 인접한 두 성냥 중 적어도 한 개는 머리가 인접해 있어야 합니다. 최소 몇 개의 성냥을 뒤집어야 할까요?
입력
표준 입력의 첫 번째 줄에는 성냥의 개수를 나타내는 하나의 정수 $n$($1 ≤ n ≤ 1\,000\,000$)가 주어집니다. 두 번째 줄은 성냥이 어떻게 놓여져 있는지를 나타내는데, $n$개의 정수 $x_1, x_2, \dots , x_n$이 공백으로 구분되어 주어집니다. 여기서 $x_i$는 $i$번째 성냥의 머리가 왼쪽에 있으면 $0$, 오른쪽에 있으면 $1$입니다.
iktk 2년 전 3
문제
당신은 성냥을 가지고 놀고 있습니다. 성냥은 선분 모양이며 둥근 쪽 끝이 머리입니다. 당신은 성냥을 일직선으로 나란히 배열했습니다. 즉, 각 성냥의 한 쪽 끝은 배열의 양 끝을 제외하고는 정확히 하나의 다른 성냥의 한 쪽 끝과 인접해 있습니다.
성냥 배열의 예시
당신은 라이터를 이용해 가장 왼쪽 성냥에 불을 붙여서 모든 성냥을 태우고 싶습니다. 인접한 성냥에 불이 옮겨 붙으려면, 인접한 두 성냥 중 적어도 한 개는 머리가 인접해 있어야 합니다. 최소 몇 개의 성냥을 뒤집어야 할까요?
입력
표준 입력의 첫 번째 줄에는 성냥의 개수를 나타내는 하나의 정수 $n$($1 ≤ n ≤ 1\,000\,000$)가 주어집니다. 두 번째 줄은 성냥이 어떻게 놓여져 있는지를 나타내는데, $n$개의 정수 $x_1, x_2, \dots , x_n$이 공백으로 구분되어 주어집니다. 여기서 $x_i$는 $i$번째 성냥의 머리가 왼쪽에 있으면 $0$, 오른쪽에 있으면 $1$입니다.
출력
방향을 뒤집어야 하는 성냥의 최소 개수를 정수로 출력합니다.
힌트