JOI 2016 2번 - スタンプラリー ２ (Collecting Stamps 2) 풀이

[JOI 2016 2번 - スタンプラリー ２ (Collecting Stamps 2)]

(원문) https://www.acmicpc.net/problem/11986

11986번: スタンプラリー ２ (Collecting Stamps 2)

(한국어 번역) https://oj.uz/problem/view/JOI16_ho_t2

문제 보기 - 스탬프 수집 (JOI16_ho_t2) :: oj.uz

 

우선 원래 문자열에서 JOI의 개수를 세어봅시다. 다음의 배열들을 이용하여 누적합을 적용해봅시다.

• J[i] : 0번째부터 i번째까지의 J의 개수 합
• O[i] : 0번째부터 i번째까지의 JO 조합 개수의 합
• I[i] : 0번째부터 i번째까지의 JOI 조합 개수의 합

첫 번째로 $0$부터 $n$까지 순회하며 J[] 배열을 채워나갑니다. 다음으로, O[] 배열을 채워나가는데, 문자열의 $k(0 \leq k < n)$ 위치에서 O가 발견된다면, O[$k$]에는 지금까지의 JO 조합 개수의 합과 J[$k$]를 더해주는 방식으로 계산하면 됩니다. 동일한 방식으로 I[] 배열도 채워나갑니다. 이때 마지막으로 채워진 값인 I[$n-1$] 값이 JOI 조합 개수의 합입니다.

 

 

쉬운 것부터 해결해봅시다.

(i) 새로운 하나의 가게가 O 스탬프를 나누어 줄 때

문자열의 $k$번째 자리와 $k+1$번째 자리 사이에 새로운 O가 들어간다고 합시다. 이때 새로 추가되는 JOI 조합의 개수는 

• 원래 문자열의 $[0, k]$에 존재하는 J의 개수와, 원래 문자열의 $[k+1, n)$에 존재하는 I의 개수의 곱

임을 알 수 있습니다. O가 JOI의 가운데 글자이기 때문에 쉽게 해결할 수 있습니다. 

 

다음의 두 경우는 (i)보다 살짝 까다롭습니다.

(ii) 새로운 하나의 가게가 I 스탬프를 나누어 줄 때

문자열의 $k$번째 자리와 $k+1$번째 자리 사이에 새로운 I가 들어간다고 합시다. 이때 새로 추가되는 JOI 조합의 개수는

• 원래 문자열의 $[0, k]$에 존재하는 JO 조합의 개수

입니다.

이는 앞서 원래 문자열에서 JOI 개수를 셀 때 사용했던 O[] 배열을 이용하면 쉽게 해결할 수 있습니다.

 

(iii) 새로운 하나의 가게가 J 스탬프를 나누어 줄 때

문자열의 $k$번째 자리와 $k+1$번째 자리 사이에 새로운 J가 들어간다고 합시다. 이때 새로 추가되는 JOI 조합의 개수는

• 원래 문자열의 $[k+1, n)$에 존재하는 OI 조합의 개수

입니다.

이 경우에는 $[0, k]$가 아닌 $[k+1, n)$에 존재하는 OI 조합의 개수를 구해야 하므로, 기존 J[], O[], I[] 배열을 이용하여 구하기가 어렵습니다. 따라서 배열의 정의를 새롭게 바꿔봅시다.

• I[$i$] : $n-1$번째부터 $i$번째까지의 I의 개수
• O[$i$] : $n-1$번째부터 $i$번째까지의 OI 조합의 개수

구하는 방식은 전과 동일하나, $0$부터 $n-1$까지가 아닌 $n-1$부터 $0$까지 순회해야 한다는 차이점이 있습니다.

 

 

이상에서, 원래 문자열에서의 JOI 조합 개수와, (i), (ii), (iii) 중 최댓값을 합한 값이 답이 됩니다.