원형으로 구슬 배치하기
골드 V의견: 0
여러 색의 구슬이 있다. 색이 \(i\) 인 구슬은 \(c_i\) 개 있다 (\(i = 1, 2, \dots, n\)). 이 구슬들 중에서 세 개 이상을 골라 원형으로 배열하려고 한다. 단, 다음 조건을 만족해야 한다.
- 원형으로 놓인 연속한 세 구슬마다, 그 중 적어도 두 개는 같은 색이어야 한다.
즉, 고른 구슬을 원형으로 \(a_0, a_1, \dots, a_{k-1}\) 순서로 놓았다면, 모든 \(i\) (\(0 \le i \le k-1\)) 에 대해 세 구슬 \(a_i,\ a_{(i+1)\bmod k},\ a_{(i+2)\bmod k}\) 중 적어도 두 개의 색이 같아야 한다.
배열할 수 있는 구슬의 최대 개수를 구하여라. 조건을 만족하도록 세 개 이상을 고를 수 없으면 \(0\) 을 출력한다.
\(1 \le n \le 2 \cdot 10^5\)
\(1 \le c_i \le 10^9\)
첫째 줄에 색의 종류 수 \(n\) 이 주어진다.
둘째 줄에 \(n\) 개의 정수 \(c_1, c_2, \dots, c_n\) 이 공백으로 구분되어 주어진다. \(c_i\) 는 색이 \(i\) 인 구슬의 개수다.
배열할 수 있는 구슬의 최대 개수를 한 줄에 출력한다.
4
2 2 2 2
8
각 색을 크기 \(2\) 인 덩어리로 두면 \([1,1,2,2,3,3,4,4]\) 처럼 모든 연속한 세 구슬에 같은 색이 둘 이상 들어간다. 모든 \(8\) 개를 사용할 수 있다.
5
1 1 1 1 6
9
색 \(5\) 의 구슬 \(6\) 개를 둘씩 묶어 \(3\) 개의 호로 나누고, 그 사이 \(3\) 곳에 서로 다른 단일 구슬을 끼워 넣을 수 있다: \([5,5,1,5,5,2,5,5,3]\). 모두 \(6+3 = 9\) 개.
3
1 1 1
0
모든 색이 한 개뿐이라 어떤 세 구슬을 골라도 같은 색이 둘이 될 수 없다. 조건을 만족하는 배열이 없으므로 \(0\).
riseoj 작성
출처 Original
평가 및 의견
원형으로 구슬 배치하기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
원형으로 구슬 배치하기