12013번 - 248 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 989 | 344 | 278 | 37.823% |
문제
Bessie는 큰 손으로 작은 터치스크린을 다루는 것이 불편함에도 불구하고 휴대폰으로 게임을 하는 것을 좋아한다.
그녀는 특히 요즘 하고있는 게임에 흥미를 느끼고 있다. 이 게임은 N개의 양수들(2 ≤ N ≤ 248)로 시작되며, 각 수는 1에서 40 사이이다. 각 수에서 Bessie는 같은 값을 가진 두개의 인접한 수를 그보다 1 큰 수 한개로 바꿀 수 있다. (예를 들어, 그녀는 두 개의 인접한 7을 8로 바꿀 수 있다.) 목표는 수열에서 더이상 합칠 수가 남아있지 않을 때, 즉 게임이 끝났을 때 수열에 있는 가장 큰 수를 최대화 하는 것이다. Bessie가 가능한 가장 높은 점수를 얻을 수 있도록 도와주어라!
입력
첫째 줄에는 N을 입력받는다.
2번째 줄부터 N개의 줄에는 게임의 시작에서 주어지는 N개의 숫자를 입력받는다.
출력
Bessie가 만들 수 있는 가장 큰 정수를 출력해라.
예제 입력 1
4 1 1 1 2
예제 출력 1
3
힌트
이 예에서, Bessie는 두 번째와 세 번째에 있는 1을 2로 합친다. (1 2 2)
두 번째와 세 번째에 있는 2를 3으로 합친다. (1 3)
첫 번째와 두 번째 1을 합치는 것은 최적해가 아님을 주의해라.
출처
Olympiad > USA Computing Olympiad > 2015-2016 Season > USACO US Open 2016 Contest > Gold 3번
- 문제를 번역한 사람: jellypudding86
- 잘못된 번역을 찾은 사람: kesakiyo
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호