https://www.acmicpc.net/problem/15831
15831번: 준표의 조약돌
첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조
www.acmicpc.net
투 포인터 문제다.
풀이
범위의 시작 인덱스를 담은 head 변수와 끝 인덱스를 담은 tail 변수를 생성. 다음과 같은 동작들을 tail이 n이 될 때까지 반복한다.
현재 tail이 가리키는 조약돌이 검은 돌이고 들고 있는 검은 돌의 개수가 B개 미만이라면, 더 들고 갈 수 있는 상태이므로 가져가야 할 돌로 포함시키고 tail을 증가시킨다.
현재 tail이 가리키는 조약돌이 검은 돌이고 들고 있는 검은 돌의 개수가 B개 이상이라면, 더 이상 들고 갈 수 없으므로 head가 가리키는 조약돌을 버리고 head를 증가시킨다.
현재 tail이 가리키는 조약돌이 흰돌이라면 가져가야 할 돌로 포함시키고 tail을 증가시킨다. 매 탐색마다 주운 조약돌의 개수가 준표의 조건에 맞다면 출력값을 최대길이로 갱신한다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [2607] 비슷한 단어 (2) | 2023.01.27 |
|---|---|
| [6503] 망가진 키보드 (0) | 2023.01.24 |
| [12892] 생일 선물 (0) | 2023.01.21 |
| [6137] 문자열 생성 (0) | 2023.01.20 |
| [22862] 가장 긴 짝수 연속한 부분 수열 (large) (0) | 2023.01.19 |