15776번 - Winter Olympic Games 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 1024 MB | 499 | 81 | 68 | 24.028% |
문제
사진: 문제와 아무 관련이 없지만, 아무튼 귀여운 수호랑.
2018 RUN@KAIST 겨울 컬링 대회의 마지막 여자 결승전이 열리는 지금, 꽁꽁 얼어붙은 오리연못에서 한국의 여자 컬링 팀은 즈웨펜(Jwepan)과 숨막히는 경쟁을 펼치는 중이다!
지금 오리연못 위에는 N개의 돌 (컬링스톤)이 놓여 있다. 두 팀의 엄청난 경쟁을 보여주듯이, 모든 돌은 과녁에서부터 일렬로 순서대로 놓여 있다. 즉, 가장 왼쪽에 있는 돌이 과녁에서 가장 가까우며, 가장 오른쪽에 있는 돌이 과녁에서 가장 멀다. 돌은 한국 대표단의 돌이거나 ('1') 즈웨펜 대표단의 돌 ('0') 이며, 이러한 돌들의 배치는 길이 N의 이진 문자열로 나타낼 수 있다.
한국 대표팀은 평창 올림픽 이후 엄청난 연습을 통해서, 이제 몇 번의 샤우팅(?) 만 해 주면, 컬링스톤을 나르는 영미가 연속해서 놓여있는 몇 개의 돌들을 전부 쳐내고, 그 자리에 자기 팀의 돌을 넣는 플레이를 할 수 있게 되었다. 즉, 한국 팀은 이진 문자열의 어떠한 구간을 골라 (구간이 문자열 전체이거나 비어있을 수 있다.) 이 구간을 "1" 으로 대체할 수 있는 능력을 가진 것이다.
오랜 연습으로 컬링 전략에 통달한 한국 팀은, 정확히 한 번의 연산을 통해서 주어진 문자열을 사전 순 최대 로 만드는 것이 게임을 하는 최선의 전략이라는 것을 깨달았다! 한국 대표단은 대회 상황에서 빠른 의사결정을 하기 위해서, 이 문제를 해결하는 가장 빠른 알고리즘을 찾고 싶어한다. 한국 대표단을 도와주자!
단, 길이 n의 문자열 s = s1s2...sn이 길이 m의 문자열 t = t1t2...tm 보다 사전순으로 크다는 것은, 다음 둘 중 하나를 만족한다는 것을 의미한다.
- 어떤 i에 대해서, s1 = t1, s2 = t_2, ..., si-1 = ti-1 이고, si > ti 이다.
- n > m이고, s1 = t1, s2 = t2, ..., sm = tm 이다.
입력
첫 번째 줄에 돌의 개수 N이 주어진다.
두 번째 줄에 길이 N의 '0' 혹은 '1'로 이루어진 이진 수열이 주어진다. 과녁에서 가까운 쪽에서 멀어지는 순서로, 각각의 돌이 어떤 팀의 소유인지를 나타낸다. '0' 혹은 '1' 사이에 공백이나 따옴표는 주어지지 않는다.
출력
두 개의 정수 S, L을 공백으로 구분하여 출력한다. 이는 영미가 S번째 문자 직후의 L개의 돌을 제거했음을 뜻한다. 만약 가능한 경우가 여럿 있으면, 이 중 아무 거나 출력해도 된다. (0 ≤ S, L ≤ N)
제한
- 1 ≤ N ≤ 1,000,000
서브태스크 1 (23점)
이 서브태스크는 다음의 조건을 만족한다.:
- N ≤ 500
서브태스크 2 (24점)
이 서브태스크는 다음의 조건을 만족한다.:
- N ≤ 10,000
서브태스크 3 (53점)
이 서브태스크는 추가 제한 조건이 없다.
예제 입력 1
8 10101101
예제 출력 1
1 3
예제 입력 2
5 11111
예제 출력 2
0 0
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호