백준 2811번. 상범이의 우울 (Java)

문제 링크 : https://www.acmicpc.net/problem/2811

해석 때문인지는 몰라도 문제를 이해하는데 살짝 어려움을 겪은 문제입니다.

 

결론을 말하자면 상범이에게 꽃을 주는 날의 최대값을 구하면 됩니다.

 

이 문제의 핵심은 다음과 같습니다.

 

1. 상범이의 우울한 정도는 상관없다. 양수, 음수인지만 판단

2. 꽃은 하루에 한개씩만 준다.

3. 꽃을 다 주지 못해도 최대한 준다. 둘째날이 우울한 날이라면 꽃은 첫째날밖에 못준다. 그래도 주자.

4. 3T만큼 꽃을 주는 날은 여러 개의 최장 우울 기간 중 한번이다.

 

문제를 해결하려면 결국 최장 우울 기간 중 가장 꽃을 많이 줄 수 있는 날이 언제인지 찾는 것이 중요합니다.

 

이걸 직접 구하는 것보다는 최장 우울 기간 전부 탐색하면서 max값을 구하는 것이 편합니다.

 

우선 모든 날에 대해서 2T만큼 꽃 주는 날을 구합니다.

 

그 후에 최장 우울 기간들만 스캔하면서 또다시 3T만큼 카운트합니다.

 

이 때 2T 구할때 체크했던 날들은 제외해서 중복 체크를 방지합니다.

 

문제에 있는 예제로 간단하게 설명해보겠습니다.

 

먼저 상범이의 우울한 날을 구합니다.

 

그림 1. 상범이의 우울한 날

그림 1에서 상범이의 최장 우울 기간은 1이고, 최장 우울 기간의 갯수는 3개입니다.

 

그럼 우선 최장 우울 기간과 관계 없이 모든 우울 기간에 대해서 2T만큼 꽃을 주겠습니다.

 

 

그림 2. 첫번째 우울한 날에 대해 꽃 주기

우울한 날이 2일이므로 0일과 1일에 꽃을 주어야 합니다.

 

하지만 보시다시피 0일은 존재하지 않습니다.

 

이 때, 위에서 언급한 핵심 3번을 보시면 꽃을 다 주지 못해도 최대한 주라는 조건이 있습니다.

 

그래서 그림 2처럼 체크하면 됩니다.

 

 

그림 3. 두번째 우울한 날에 대해 꽃 주기

그리고 두번째로 우울한 날에 대해서 꽃을 줍니다.

 

그림 3처럼 4일과 5일에 꽃을 줄 수 있습니다.

 

 

 

그림 4. 세번째 우울한 날에 대해 꽃 주기

마지막으로 우울한 날에 대해서 꽃을 줍니다.

 

8일이 우울한 날이기 때문에 6일과 7일에 꽃을 줍니다.

 

여기서 헷갈릴 수 있는 요소가 하나 있는데 우울한 날과 관계없이 꽃은 줄 수 있습니다.

 

따라서 그림 4처럼 2T만큼 모든 우울한 날에 대해서 체크를 하였습니다.

 

2T를 전부 체크한 시점에서 꽃을 주는 날의 count는 5 입니다.

 

 

 

그림 4. 3T 구하기

이제 3T의 최대값을 구해야 합니다.

 

최장 우울 기간에 해당하는 모든 우울한 날에 대해서 3T를 구합니다.

 

첫번째 날은 보시다시피 꽃을 더 줄 수 없습니다.

 

add는 0 입니다.

 

 

 

그림 5. 3T 구하기 - 2

두번째 우울한 날에 대해서 3T를 구합니다.

 

우울 기간이 1이기 때문에 꽃을 하루 더 줄 수 있습니다.

 

이때, 꽃을 줄 수 있는 날은 카운트만 하고 표시는 하지 않습니다.

 

3T는 모든 여러가지 최장 우울 기간 중 단 한번만 주면 되기 때문입니다.

 

만약 최장 우울 기간이 1이 아니라 3 정도 되고 3T를 구할때마다 모든 날에 체크를 한다면 뒤에 나오는

 

최장 우울 기간에는 꽃을 줄  수 있는 날이 없을수도 있고, 그럼 모든 경우의 수를 알 수 없습니다.

 

아무튼 여기서 add는 1이고 기존의 count 5와 더해서 max 값을 6으로 갱신합니다.

 

 

그림 6. 3T 구하기 - 3

마지막 우울한 날에 대해서 3T를 구합니다.

 

하지만 이미 3일 전인 5, 6, 7일 전부 꽃을 주기로 되있으므로 꽃을 더 줄 필요가 없습니다.

 

따라서 추가로 주는 꽃은 없고 add는 0입니다.

 

 

 

그림 7. 최종

최종적으로 꽃을 주는 날은 위와 같고 최대값은 6이 됩니다.

** 코드에서는 뒤에서부터 돌면서 미리 꽃을 주었습니다.