# [Gold II] 접시 포개기 [문제 링크](https://www.acmicpc.net/problem/30410) ## 문제 설명 <p>춘배는 배가 너무 고파서 밥을 모두 먹어 치웠고 현재 춘배의 앞에는 $N$개의 접시가 있다. $i$번째 접시의 두께는 정수 $A_i$로 표현되는데, 이제 배부르기 때문에 재미있는 놀이를 해보려고 한다.</p> <p style="text-align: center;"><img alt="" src="https://upload.acmicpc.net/979b602e-9058-4fb8-92fa-a4a6cd640f84/-/preview/"></p> <p>다음과 같이 접시를 포갤 수 있을 때, 마지막에 남는 가장 두꺼운 접시의 두께를 최대화하는 것이 목표이다.</p> <ul> <li>두께가 같은 인접한 두 접시를 포개어 두께가 $2$배가 된 새로운 접시를 그 자리에 놓는다.</li> </ul> <p>진짜로 접시를 포개면 깨질 수 있기 때문에 춘배는 당신의 도움을 얻고자 한다. 마지막에 남는 가장 두꺼운 접시의 두께를 최대화해보자!</p> ## 입력 <p>첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 2 \times 10^5)$</p> <p>두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백을 사이에 두고 주어진다. $(1 \le A_i \le 2)$</p> ## 출력 <p>남아있는 가장 두꺼운 접시의 두께의 최댓값을 출력한다.</p> ## 풀이 - 2가 들어올 때는 이전 그룹에 합친다. - 1이 들어올 때는 2로 전부 바꿔서 이전 그룹에 합친다. - 1이 짝수 개 연속적으로 등장한 경우 전부 2가 들어왔다 생각하고 그룹을 그대로 이어나간다. - 1이 홀수 개 연속적으로 등장한 경우 2로 바꾼 개수로 새로운 그룹을 시작한다. ``` c++ #include<bits/stdc++.h> using namespace std; int blockMerge(int n) { int ret=1; while(ret<=n) ret<<=1; return ret; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int res=0, last1=0, last2=0; while(n--) { int cur; cin >> cur; if(cur==1) last1++; else { last2++; if(last1%2) last2 = last1/2; else last2 += last1/2; last1=0; } res = max(res, last2+last1/2); } cout << blockMerge(res); } ```