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

풀이 아이디어

입력을 받으면서 기분을 나타낸 정수값을 emotion이라고 하면
emotion>=0이면 기분 좋은 날로 처리하고
emotion<0이면 기분 우울한 날로 간주한다.

• int[] sadDays: 연속된 우울한 날을 저장한다.
• int longestSad: 가장 긴 우울한 기간을 저장한다.
• boolean[] isGiveFlower: 꽃을 주었는지 확인하는 배열
• int needFlower: 모든 우울한 기간에 시작일 전부터 2T일전까지 준다고 가정했을 때 주는 꽃의 수
• int plusGive: 최장 우울한 기간 중에서 2T+1부터 3T일 전까지 줬을 때 추가로 주는 꽃의 갯수

1. 인덱스 0~n-1까지 순회하며 연속된 우울한 날을 계산해 int[] sadDays에 저장한다.
   예를 들어 기분이 좋은 날이면 0이지만, 우울한 기간 중 첫날이면 1, 둘째날이면 2인 식이다.
2. 인덱스 n-1~0까지 sayDays 배열을 뒤에서부터 순회하며
   sayDays>0이면 우울한 기간이 시작된다는 의미이므로, 우울한 기간이 T라면
   우울한 기간이 시작되기 전날부터 2T일전까지 꽃을 준다. 이때 isGiverFlower[i]=true로 해준다.
3. 다시 int[] sadDays을 뒤에서부터 순회하며
   최장 우울한 기간을 나나태는 값 longestSad에 해당하는 기간의 2T+1일전부터 3T일전까지
   isGiverFlower[i]=false인 날의 수를 계산한 다음
   가장 많이 꽃을 줄 수 있는 최장 우울한 기간에 3T로 주는걸로 간주해서
   실제로 추가로 주는 꽃의 수 int plusGive의 최대값을 구한다.

전부 2T로 꽃을 준 갯수 needFlower에 plusGive를 더하면 정답이다.

추가 테스트 케이스

백준 문제에 제시된 예제 입출력은 통과하는데 문제는 틀리길래
대회 테스트 케이스를 통해 검증을 해보니 0도 입력에 있었다.
0은 우울한 날은 아니므로 기분좋은 날과 동일시해줘야 한다.

입력
391
-6 -18 -25 -33 -6 -33 -72 -77 5 -33 -61 -49 -87 -75 -58 37 71 0 59 60 9 5 20 57 28 48 93 41 73 42 49 60 3 92 58 81 56 -25 -83 -12 -98 -47 23 -97 17 -93 -36 -19 -73 -61 -4 34 -16 -16 -23 95 69 31 17 13 40 70 24 56 45 23 97 13 33 52 29 8 0 20 38 68 42 14 95 41 11 12 47 86 -42 -1 54 -7 -39 -24 -55 -87 -26 37 -66 -4 -72 -40 -18 -84 94 -10 -87 -94 -70 -65 -26 92 -15 12 -26 -53 -30 -67 52 86 3 27 14 87 97 22 66 68 21 17 74 72 75 20 48 40 35 4 88 66 44 0 38 57 5 81 26 95 34 97 6 53 26 15 15 34 40 48 54 5 63 29 43 52 6 74 51 47 35 87 43 14 45 52 13 43 96 36 42 98 76 3 64 22 78 1 36 65 85 25 61 12 95 17 -20 84 -31 -9 -19 -33 -1 85 -80 -81 -72 2 -26 -74 -9 86 17 -35 -56 5 -7 -58 87 31 56 3 62 91 -17 -38 -65 -49 -34 54 -59 -82 -9 31 -60 -71 86 -39 -38 -28 -28 -37 -84 27 -74 -7 73 -87 -28 -95 -86 -46 -57 -61 30 18 83 0 57 13 24 56 66 3 28 77 4 33 25 39 71 30 37 75 45 71 70 85 53 36 55 96 56 68 11 86 21 38 56 67 68 15 40 60 65 81 73 43 32 38 18 74 90 86 90 84 54 39 43 6 62 76 79 92 48 10 69 47 67 85 67 69 18 94 56 44 63 21 48 65 97 2 87 10 99 31 99 35 9 29 86 2 97 6 59 74 55 62 7 98 86 3 35 99 94 12 21 55 44 55 80 -27 -52 -33 -82 17 -77 79 -97 42 -34 -27 -32 80 69 -23 90 -82 -68 -37 -19 -40 19 -31 -45 -95 -11 68 -69 -18 -74 15 -68 -44 -39 -25 -66

출력
161

입력
942
-83 -89 -18 -27 -12 55 -15 -10 -39 33 -76 46 -17 -79 -41 -31 -63 21 -85 -49 -6 39 -69 -24 30 -84 81 -27 -31 64 -50 -87 89 -15 49 -71 -92 1 -98 -30 -5 -40 -1 67 -64 18 -39 -17 65 -34 -97 66 -25 -40 -79 -14 38 -9 -11 -15 -73 -75 48 -54 -95 -2 -24 6 -2 -93 -60 64 -71 -91 -3 20 -78 -35 75 -34 62 -18 -43 82 -90 -70 -96 39 -63 -53 -74 -72 1 -97 57 -7 -17 17 -27 -7 -47 -16 -21 6 -34 -88 -61 -45 76 -30 -64 -20 -68 3 -49 -19 86 -30 -81 8 -99 -50 -35 -11 83 -88 -93 54 -94 -1 -48 -48 39 -81 86 -53 -21 -26 -98 -61 60 -99 -35 -52 -7 -43 12 -58 -65 -83 -12 45 -17 -20 -1 -95 35 -67 -62 10 -51 -68 -36 -57 -11 21 -63 -71 -89 -25 25 -6 -92 8 -10 -17 -97 17 -25 -44 -8 70 -46 -91 -56 66 -48 -14 85 -22 -91 -55 -54 11 -76 -60 -96 -6 2 -38 -38 -53 -6 65 -66 -66 -99 -26 92 -87 -50 -95 -48 -2 2 -10 -72 -73 89 -12 -42 44 -33 -5 6 -61 -36 -73 45 -74 -8 -56 -55 63 -37 -15 -64 -58 -97 85 -25 -61 5 -67 18 -66 -14 -98 31 -44 -62 52 -3 -31 -79 -87 -45 31 -91 -95 7 -96 -61 -1 26 -38 84 -37 -38 -41 48 -50 -16 -87 -62 -85 60 -97 -63 -89 1 -74 -7 -55 75 -47 -28 -67 -55 -51 73 -61 -94 -47 -9 -10 25 -59 -3 -70 57 -44 -81 -59 -89 -97 27 -21 -91 -38 -4 2 -71 43 -44 -16 -78 -10 -96 37 -3 -39 25 -61 -38 -57 66 -32 -39 -49 70 -33 -60 -87 40 -40 -61 -71 -27 48 -39 -23 80 -6 -48 -77 27 -95 -23 6 -79 -64 -67 -74 85 -20 58 -36 -94 -49 0 -73 -61 -57 88 -89 -27 -93 -67 31 -19 -57 -28 -33 -88 92 -48 -25 17 -68 -48 -14 -59 -21 17 -99 -37 -37 -66 57 -69 -61 -82 80 -4 -15 -9 13 -72 -86 -10 -36 -62 25 -50 -10 -20 -75 -45 29 -85 -87 35 -65 86 -46 -22 -87 -48 52 -22 -93 59 -19 -38 27 -14 -55 -99 -72 23 -48 -72 43 -91 -32 51 -73 -93 -2 -88 -83 59 -89 -99 -42 54 -9 -19 -54 13 -74 -66 64 -52 -97 -75 16 -75 -61 -52 -66 -25 40 -64 -82 -28 46 -56 -14 -96 -21 -19 44 -23 -74 -33 -97 -33 90 -53 -63 4 -45 -34 62 -59 -38 -76 -97 -32 56 -58 -20 78 -11 -72 -76 80 -2 5 -40 -90 46 -54 -31 -78 81 -55 -7 -50 -79 -26 52 -99 -47 -52 -44 -23 14 -52 -94 -37 -68 87 -91 -84 -46 -30 -30 12 -35 -35 -96 49 -8 -47 -44 -32 -99 8 -88 -71 -96 52 -71 -12 -95 -1 -25 82 -49 -84 63 -86 -81 -23 -87 77 -21 67 -97 -32 -52 -27 -72 87 -65 46 -82 26 -91 -23 -89 7 -84 85 -42 -25 -24 70 -80 -29 -99 -81 27 -74 -80 -71 54 -8 5 -99 20 -50 67 -64 -45 46 -65 -41 -34 -66 26 -82 -18 -88 -50 20 -84 -41 -2 -18 76 -83 38 -32 -12 -73 -73 -97 38 -89 -84 75 -18 -10 -84 -26 -13 9 -8 -38 -62 -13 7 -69 -94 -59 -37 26 -37 75 -86 -51 -46 -71 -70 40 -4 24 -34 -11 -87 -65 -66 72 -99 1 -63 71 -15 81 -63 -96 -96 -25 -95 78 -52 41 -72 -25 -8 -53 67 -89 -18 -41 -77 46 -17 -60 -77 -66 -40 66 -56 -12 -98 84 -58 -78 -54 -19 95 -99 -50 -36 -22 -9 26 -27 -26 18 -31 -75 -92 45 -50 -13 -94 -12 31 -15 -87 -74 3 -98 69 -71 -66 -84 3 -23 -83 21 -27 2 -30 9 -95 -96 -74 -78 73 -33 -18 -43 -19 -24 16 -49 -68 -14 -60 17 -28 -99 -67 -64 -56 45 -31 -68 -94 -79 13 -8 -13 -87 -89 -34 78 -36 -46 -86 74 -81 -45 -87 -20 72 -17 -56 -40 -44 41 -88 -71 39 -56 55 -37 -8 -54 -82 66 -70 -57 -83 24 -99 -19 -66 -24 18 -28 71 -85 -29 41 -63 61 -18 -17 -37 -2 40 -5 4 -79 -53 -40 88 -58 -50 -50 -90 -61 56 -46 -78 -49 -22 60 -30 -60 -94 39 -95 -83 -70 92 -21 -44 -17 -58 -86 51 -29 -37 -83 61 -51 -66 -72 -28 84 -52 -28 -28 -57 47 -81 -54 7 -25 -98 -59 -94 36 -13 -7 -65 29 -75 -26 -33 -83 62 -63 -11 -79 -58 5 -25 -58 -66 -97 56 -80 19 -46 -94 31 -29 -97 -92 -45 86 -25 3 -17 72 -98 -96 -67 -20 5 -54 -52 -12 -23 38 -23 -79 -89 -67 -43 59 -42 -50 -2 -88 -51 30 -40 -7 -12 -92 16 -59 55 -49 -90 57 -84 -79 -19 -76 -96 37 -47 -38 -94 40 -1 -26 -79 -30 -24

출력
894

트러블슈팅

예제 입출력도 다 통과하고 일반화를 잘해서 푼 거 같은데 안 되길래
뭐가 문제지하고 보니까 그날 기분을 표현한 정수값 emotion을 처리하는데 문제가 있었다.
emotion==0은 우울한 날이 아니므로 기분 좋은 날과 똑같이 처리를 해줘야했다!!

emotion==0일 때도 기분 좋은 날로 간주하니 문제가 해결되었다.
"if(emotion > 0)" -> "if(emotion >= 0)"

for(int i=0;i<n;i++){
    emotion = Integer.parseInt(st.nextToken());
    // 0은 우울한 날이 아니기 때문에 기분 좋은 날로 간주한다.
    if(emotion >= 0){ 
        sadCount = 0;
        sadDays[i] = sadCount;
    }
    else{
        sadCount++;
        sadDays[i] = sadCount;
    }
}

해결한 코드

import java.io.*;
import java.util.*;

public class _2811 {
    public static void main(String[] args) throws IOException{
        // 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int emotion = 0; // 오늘 기분
        int sadCount = 0;

        int[] sadDays = new int[n]; // 각 날짜별로 연속된 우울한 날의 수를 저장하는 배열
        // 연속된 우울한 날의 계산해서 sadDays 배열에 저장한다.
        for(int i=0;i<n;i++){
            emotion = Integer.parseInt(st.nextToken());
            // 0은 우울한 날이 아니기 때문에 기분 좋은 날로 간주한다.
            if(emotion >= 0){ 
                sadCount = 0;
                sadDays[i] = sadCount;
            }
            else{
                sadCount++;
                sadDays[i] = sadCount;
            }
        }

        // 우울한 기간이 T라면 우울한 기간이 시작 전날~2T일까지 꽃을 준다.
        boolean[] isGiveFlower = new boolean[n]; // 각 날짜별로 꽃을 주었는지 확인하는 배열
        int needFlower = 0; // 필요한 꽃의 수
        int longestSad = 0; // 최장 우울기간
        // 뒤에서부터 우울한 날을 찾아 2T일 전까지 꽃을 준다.
        for(int i=n-1;i>=0;i--){
            // 최장 우울기간 찾기
            if(sadDays[i] > longestSad){
                longestSad = sadDays[i];
            }

            // 우울한 날의 수가 0이 아니라면 2T일까지 꽃을 준다.
            if(sadDays[i]>0){
                for(int j=i-sadDays[i];j>=i-3*sadDays[i]+1;j--){
                    if(j<0) break;

                    if(isGiveFlower[j] == false){
                        isGiveFlower[j] = true;
                        needFlower += 1;
                    }
                }
                i -= sadDays[i];
            }
        }

        // 최장 우울기간에 추가로 줘야하는 꽃의 수를 찾는다. 
        // 최장 우울기간이 여러개라면 추가로 줘야하는 꽃의 수가 가장 많은 것을 선택한다.
        int plusGive = 0; // 최장길이일 때 추가로 줘야하는 꽃의 수
        for(int i=n-1;i>=0;i--){
            if(sadDays[i] == longestSad){
                int count = 0;
                // 2T+1~3T까지의 false의 갯수를 센다.
                for(int j=i-3*longestSad;j>=i-4*longestSad+1;j--){
                    if(j<0) break;
                    if(isGiveFlower[j] == false){
                        count += 1;
                    }
                }
                // 최장 우울기간일 때 추가로 주는 꽃의 수의 갱신하며 최대값을 찾는다.
                if(count > plusGive){
                    plusGive = count;
                }
            }
        }
        System.out.println(needFlower+plusGive);
    }
}