[BOJ_C++] 2811번 : 상범이의 우울

예제 풀이
문제 : 1 -1 4 3 8 -2 3 -3
꽃 :    *  0 *  *  *  *  * 0
-> '*'가 꽃을 주는 날이다.
-> 우울한 기간에도 꽃을 받을 수 있다. 단, 구간의 시작 바로 전날까지 꽃을 선물해야 그의 우울함을 덜어줄 수 있으므로 우울 기간에 받은 꽃은 다음 우울 기간부터 효력이 나타난다.

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>
#include <string>

using namespace std;
int list[100001];
char check[100001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(list, true, sizeof(list));
    int n, len = 0, maxl = 0, cnt = 0, maxday = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> list[i];
    }
    
    for (int i = 0; i <= n; i++) {
        if (list[i] < 0) {
            len++;
            continue;
        }
        if (len == 0) continue;
        maxl = max(maxl, len);
        for (int j = i - len - 1; j > i - len * 3 - 1; j--) {
            if (j < 0) break;
            check[j] = '*';
        }
        len = 0;
    }

    for (int i = 0; i <= n; i++) {
        if (list[i] < 0) {
            len++;
            continue;
        }
        if (len == maxl) {
            for (int j = i - len - 1; j > i - len * 4 - 1; j--) {
                if (j < 0) break;
                if (check[j] == '*') continue;
                cnt++;
            }
            maxday = max(maxday, cnt);
        }
        len = cnt = 0;
    }
    
    /*
    for (int i = 0; i < n; i++) {
        if (check[i] == '*')
            cout << check[i] << " ";
        else
            cout << "- ";
    }
    */

    for (int i = 0; i < n; i++)
        if (check[i] == '*') ++maxday;

    cout << maxday;

    return 0;
}

 

• 처음 for문에서는 2T 구간을 먼저 계산하게 된다.
  • 먼저 우울기간 len를 구한다. 이때 최장 우울기간인 maxl도 같이 계산해둔다.
  • 꽃을 받는 마지막 날 부터 거꾸로 꽃을 주는 날을 채워 갈 것이다. 즉, j = i - len - 1 부터 j > i - len * 3 - 1까지 꽃을 채워준다.
    • j > i - len * 3 -1 까지인 이유는 j 의 시작 인덱스가 i - len - 1이고 여기서 len * 2만큼 더 뒤까지 꽃을 줘야하기 때문이다.
  • 꽃을 다 채운 후 len을 0으로 초기화하여 다른 경우도 구할 수 있도록 한다.
• 두 번째 for문에서는 3T 구간을 계산해야하는데 이때 최장 우울기간은 여러 개가 될 수 있다. 따라서 꽃을 채우는 방식이 아닌 최장 기간에서 꽃을 추가할 수 있는 날의 수를 계산할 것이다.
  • 우울기간을 구하여 앞서 구해둔 최장 우울기간과 길이가 같다면 이미 꽃이 채워진 날을 제외하고 채울 수 있는 날(maxday)을 계산한다.
    • j > i - len * 4 - 1까지인 이유는 len * 3 만큼 더 뒤까지 꽃을 줘야하기 때문이다.
• 세 번째 for문에서는 꽃이 있는 날을 maxday에 카운트하여 더해주면 된다.
• 이후 maxday를 출력하고 프로그램을 종료한다.

결과