시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 643 | 158 | 138 | 27.112% |
배고픈 다오는 신메뉴인 트리플 멕스 버거를 먹기 위해서 멕스날드에 갔다. 마침 멕스날드는 신메뉴를 낸 기념으로 트리플 멕스 게임에서 높은 점수를 얻으면 단품을 세트로 업그레이드 해주는 이벤트를 진행하고 있었고, 다오는 게임에 참여하기로 했다.
트리플 멕스 게임은 주어지는 길이 $N$의 배열 $A$와 빈 배열 $B, C$로 시작한다. 플레이어는 두 가지 행동을 할 수 있다.
이때 플레이어가 얻게 될 점수는 배열 $C$에 존재하는 모든 원소들의 mex값이다. subsequence, subarray, mex의 정의는 힌트를 참고할 수 있다.
다오는 자신이 얻을 수 있는 최고 점수를 미리 계산하여 높은 점수를 얻을 수 없으면 굳이 참여하지 않으려고 한다. 다오를 도와서 다오가 주어진 배열 $A$에 대해서 얻을 수 있는 최고 점수를 계산해보자!
첫째 줄에는 배열 $A$의 길이 $N$이 주어진다.
둘째 줄에는 배열 $A$의 원소 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다.
모든 입력은 정수이다.
다오가 얻을 수 있는 최대 점수를 출력한다.
5 0 7 3 2 1
6
어떤 배열의 Subsequence는 주어진 배열에서 0개 이상의 원소를 제거하여 만들어진 배열을 의미한다. 단, 이 문제에서 빈 배열은 Subsequence가 아니다.
어떤 배열의 Subarray는 주어진 배열의 연속된 부분을 의미한다. 단, 이 문제에서 빈 배열은 Subarray가 아니다.
어떤 배열의 mex는 배열에서 나타나지 않는 0 이상의 가장 작은 정수이다. 추가적인 설명은 https://en.wikipedia.org/wiki/Mex_(mathematics) 를 참조하면 된다.
Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 3 B번