병제는 매일 $n$개의 강의를 듣는 대학생입니다. 병제같은 알고리즘 전문가에게는 대부분의 강의가
너무나도 지루하기 때문에, 커피를 마시지 않고서는 버틸 수가 없습니다. 하나의 강의를 듣기 위해 꼭 한 잔의 커피가 필요합니다.
일부 강의실에는 커피 머신이 있어 병제는 항상 그 곳에서 커피를 마실 수 있습니다. 또한 병제는 강의실을 떠날 때 다음 강의를 위해 최대 두 개의 커피 잔을 가져갈 수 있습니다(양손에 한
잔). 병제는 쉬는 시간 동안 두 개보다 많은 커피 잔을 옮길 수 없다는 점에 유의하십시오.
병제의 강의실 중 커피 머신이 있는 곳이 주어질 때, 병제가 깨어 있을 수 있는 최대 강의 수를 계산해야 합니다.
입력
첫 번째 줄에는 병제가 듣는 강의의 개수 정수 $n (1 \le n \le 10^5)$이 주어집니다.
두 번째 줄에는 길이가 $n$인 문자열 $s$가 주어집니다. $i$번째 강의실에 커피 머신이 있다면 1, 그렇지 않다면 0으로 표기됩니다.
w8385 3년 전 6
문제
병제는 매일 $n$개의 강의를 듣는 대학생입니다. 병제같은 알고리즘 전문가에게는 대부분의 강의가 너무나도 지루하기 때문에, 커피를 마시지 않고서는 버틸 수가 없습니다. 하나의 강의를 듣기 위해 꼭 한 잔의 커피가 필요합니다.
일부 강의실에는 커피 머신이 있어 병제는 항상 그 곳에서 커피를 마실 수 있습니다. 또한 병제는 강의실을 떠날 때 다음 강의를 위해 최대 두 개의 커피 잔을 가져갈 수 있습니다(양손에 한 잔). 병제는 쉬는 시간 동안 두 개보다 많은 커피 잔을 옮길 수 없다는 점에 유의하십시오.
병제의 강의실 중 커피 머신이 있는 곳이 주어질 때, 병제가 깨어 있을 수 있는 최대 강의 수를 계산해야 합니다.
입력
첫 번째 줄에는 병제가 듣는 강의의 개수 정수 $n (1 \le n \le 10^5)$이 주어집니다.
두 번째 줄에는 길이가 $n$인 문자열 $s$가 주어집니다. $i$번째 강의실에 커피 머신이 있다면
1, 그렇지 않다면0으로 표기됩니다.출력
병제가 깨어 있을 수 있는 최대 강의 수를 출력합니다.