# [Gold I] 점 칠하기 [문제 링크](https://www.acmicpc.net/problem/1409) ## 문제 설명 <p>다솜이는 친구가 없는 왕따이기 때문에, 혼자 노는 놀이는 거의 다 완벽하게 익혔다. 하지만, 다솜이가 정복하지 못한 놀이가 하나 있었다. 바로 어떤 원 위에 점을 색칠하면서 노는 것이다.</p> <p>다솜이는 원 위에 2N개의 점을 찍어놓고, 각각의 점을 빨간색과 파란색으로 칠하려고 한다. 다솜이는 그냥 칠하는 것은 왕따의 본분에 맞지 않다고 생각했기 때문에, 규칙을 정했다.</p> <p>다솜이가 정한 규칙은 빨간색으로 칠한 점들을 어떤 각도로 일정하게 돌리면 파란색점과 겹쳐진다는 것이다.</p> <p>예를 들어, 어떤 원에서 0, 10, 15, 25, 40, 50도에 점이 있다면, 0, 15, 40도를 빨간색으로 칠하고, 10, 25, 50를 파란색으로 칠하면, 빨간색으로 칠한 점을 10도씩 돌리면 파란색과 겹쳐지게 된다.</p> <p>하지만, 다솜이는 어떤 점을 찍었을 때 항상 위와 같이 칠할 수 없다는 것을 깨달았다.</p> <p>원위의 점의 위치가 각도로 주어졌을 때, 다솜이의 규칙에 맞게 칠할 수 있는 점의 최대 개수를 구하는 프로그램을 작성하시오. </p> ## 입력 <p>첫째 줄에 원 위에 찍혀있는 점의 개수 N (1 ≤ N ≤ 360)이 주어진다. 다음 줄부터 N개의 줄에 점이 찍혀있는 각도가 한 줄에 하나씩 주어진다. 각도는 0보다 크거나 같고, 359보다 작거나 같다. 각도는 중복되어 들어오지 않는다.</p> ## 출력 <p>첫째 줄에 색칠할 수 있는 점의 최대 개수를 출력한다.</p> ## 풀이 빨간색과 파란색의 각도 차이의 범위가 1~359이기 때문에 빨간색과 파란색의 각도 차이를 1부터 359까지 브루트포스 돌리면 됩니다. 초기 각도에서 diff 간격으로 다음 각도로 계속 이동하다 보면 이미 방문하지 않았던 각도만 방문하며 초기 각도로 돌아오기에 원은 여러 사이클로 나뉜다고 볼 수 있습니다. diff 간격으로 점을 순회할 때, 연속해서 색칠할 수 있는 칸의 길이가 i라면 빨간색 i/2개, 파란색 i/2개를 색칠할 수 있어 i가 홀수라면 i-1개, 짝수라면 i개를 색칠할 수 있습니다. 모든 사이클에 대해 값들을 더하면 됩니다. 추가로 원형 구조라서 사이클의 처음과 끝이 이어지는 경우도 고려해야 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; bool ang[360], use[360]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(n--) { int x; cin >> x; ang[x]=true; } int maxCnt=0; for(int diff=1;diff<360;diff++) { int cnt=0; memset(use, 0, sizeof use); for(int start=0;start<360;start++) { if(use[start]) continue; int cur=start, len=0; vector<int> lens; do { if(ang[cur]) len++; else { lens.push_back(len); len=0; } use[cur]=true; cur = (cur+diff)%360; } while(cur!=start); if(lens.empty()) lens.push_back(len); else lens[0] += len; for(int e : lens) cnt += e/2*2; } maxCnt = max(maxCnt, cnt); } cout << maxCnt; } ```