시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 270 | 83 | 73 | 36.500% |
각고의 노력 끝에 현자의 돌을 얻은 연금술사는 모든 물질로 금을 만들 수 있는 것은 아니라는 사실을 깨닫고 절망하였다. 그러나, 그는 현자의 돌을 이용해 가치가 낮은 광물로 가치가 높은 광물을 만들 수 있다는 사실을 발견하였다. 물론, 가치가 높은 광물을 사용해서 얻은 결과물의 가치가 낮을 수도 있다.
구체적으로, 광물 k(k ≥ 1)개와 현자의 돌을 이용해 새로운 광물을 만드는 경우를 생각해 보자. 사용한 광물 k개의 가치를 각각 x1, x2, …, xk라 할 때, S = {x1, x2, …, xk}에 포함되지 않는 가장 작은 음이 아닌 정수 MEX(S)가 최종 산물의 가치가 된다. 예를 들어, 가치가 각각 0, 1, 4, 2, 1인 광물과 현자의 돌을 이용해 새로운 광물을 만드는 경우, MEX({0, 1, 4, 2, 1}) = 3이므로 결과 광물의 가치는 3이 된다.
현재 연금술사는 가치가 0, 1, 2, …, (N − 1)인 광물들을 각각 c0, c1, c2, …, cN-1개씩 가지고 있다. 연금술사는 이 광물들과 현자의 돌을 이용해 새로운 광물을 만드는 과정을 여러 번 반복할 수 있다. 결과물로 나온 광물도 다시 재료로 사용할 수 있다. 이 과정에서 현자의 돌은 무한히 사용할 수 있다.
연금술사의 목표는 최종적으로 단 하나의 광물만을 남기면서 그 광물의 가치를 최대로 하는 것이다. 단, 광물을 사용하지 않고 버릴 수는 없다.
연금술사가 최종적으로 얻게 될 단 하나의 광물의 가치의 최댓값을 구하여라.
첫 줄에 정수 N이 주어진다.
두 번째 줄에 N개의 정수 c0, c1, …, cN-1이 공백으로 구분되어 주어진다. 단, 연금술사는 적어도 하나 이상의 광물을 갖고 있다.
첫 줄에 최종적으로 남은 광물 하나의 가치의 최댓값을 출력한다.
1 1
1
2 0 1
1
6 1 0 0 0 0 1
2
5 0 0 0 0 1
4
5 1 0 1 0 1
3
다음은 다섯 번째 예제에 대한 설명이다.
처음에는 가치가 0, 2, 4인 광물이 하나씩 존재한다.
가치가 0인 광물과 현자의 돌을 이용해 가치가 MEX({0}) = 1인 광물을 만들면 남은 광물들의 가치는 1, 2, 4가 된다.
가치가 4인 광물과 현자의 돌을 이용해 가치가 MEX({4}) = 0인 광물을 만들면 남은 광물들의 가치는 0, 1, 2가 된다.
가치가 0, 1, 2인 광물과 현자의 돌을 이용해 가치가 MEX({0, 1, 2}) = 3인 광물을 만들면 가치가 3인 광물 하나만 남고, 이것이 남은 광물의 가능한 최대 가치이다.
University > 서울대학교 > 2020 서울대학교 프로그래밍 경시대회 > Division 1 I번
Contest > Open Cup > 2020/2021 Season > Stage 3: Grand Prix of Korea H번