백준 2811 자바 - 상범이의 우울 (BOJ 2811 JAVA)

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

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02800/BOJ_2811.java

 

  정리하자면 결국 다음과 같다.

1. 연속된 음수 날의 개수(우울 기간)를 센다.

2. 해당 우울 기간 * 2 배 이전부터 꽃을 준다.

3. 그 중 가장 우울 기간이 긴 날들을 살펴보면서, 3배 이전부터 선물을 줬을 때 가장 많은 꽃을 사줘야 하는 경우를 고르면 된다.

 

  그럼 내가 푼 로직은 다음과 같다.

1. 배열로 값들을 입력받는다.

 

2. 연속된 음수값에 대해 해당 음수값이 시작한 위치에 '우울 기간(T)'을 기입한다. 다음의 경우를 보자.

 

15

-4 2 5 -1 -3 4 -5 6 1 5 8 3 -1 -2 1

 

과 같이 입력이 들어온 경우이다.

위와 같이 T가 적힐 것이다. (코드의 arr[]이 T 에 해당한다.)

이 때, 가장 긴 T에 대한 리스트를 유지하자. 위의 경우라면 가장 긴 T가 2 이므로, idx 기준으로 3과 12를 기록해둔다. (코드의 maxIdxs)

 

3. 그럼 이제 다시 확인하며, 0이 아닌 위치에 대해 -2T부터 선물을 준다고 채킹한다. 당연하지만 중복되더라도 당일에 2번 줄 필요는 없다. 따라서 boolean 배열로 체킹하는게 좋다.(코드의 day[])

음영 처리된 부분이 꽃을 줘야 하는 날이다.

 

4. 이제 '2'에서 처리해둔 가장 긴 T에 대한 위치정보를 전부 확인하면서 3T까지 더 줬을 때 음영처리를 추가로 더 많이 할 수 있는지를 보면 된다.

 

4.1 idx 3 을 우선 보자. 이 경우 추가로 더 선물을 줄 수 없다.

 

4.2 다음으로 idx 12를 보자.

이 경우 노란색으로 음영처리한 부분에 추가로 꽃을 줄 수 있다. 따라서 이 경우를 고르면 된다. 그럼 최종적으로 음영처리된 곳을 세보면 11이 답이 된다.