[코드포스 Practice21] B. Alice and Hairdresser

문제를 이해 못 해서 못 풀었다

 

길이 최대 l 만큼 자르고 싶은 것도 알겠고 가위 한 번 자르면 l 만큼 잘리는 것도 알겠는데

 

마지막의 예시를 보면 그렇게 안 잘리는 것 같아서 당황했다. 

 

길이가 l보다 긴게 연속으로 있으면 한번에 잘리는 조건이 추가로 있었다 ㅠ__ㅠ 아 영어 답답해

 

 With one swing of the scissors the hairdresser can shorten all hairlines on any segment to the length l, given that all hairlines on that segment had length strictly greater than l

 

이 문장이 그걸 나타내는 것 같은디 아 답답해 그래도 해석 안 돼

 

 With one swing of the scissors the hairdresser can shorten all hairlines on any segment to the length l

 

여기서 가위질 한 번에 모든 머리카락을 자를 수 있다는 것 같고

 

given that all hairlines on that segment had length strictly greater than l

 

그 부분의 머리카락은 I 보다 길어야 한다는 것 같다.

 

 

풀이는 계속 N^2으로 구하는 방법 밖에 모르겠고 뭔가 바뀌는 것만 어떻게 하면 될 것 같은데 감이 안 잡혀서 풀이만 봤다.

 

이걸 묶음의 개수 변화로 체크하면 좋다

 

구현은 l 이상인 거 체크하는 배열과 묶음의 개수 저장하는 변수 두 개 둬서 구현했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n, m, l;
    scanf("%d %d %d", &n, &m, &l);
    
    vector<int> check(n, 0);
    vector<i64> v(n, 0);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &v[i]);
        
        if (v[i] > l)
        {
            check[i] = 1;
        }
    }
    
    int group = 0;
    bool is_one = false;
    
    for (int i = 0; i < n; i++)
    {
        if (check[i] == 1 && !is_one)
        {
            group++;
            is_one = true;
        }
        else if (check[i] == 0 && is_one)
        {
            is_one = false;
        }
    }
    
    for (int i = 0; i < m; i++)
    {
        int t;
        scanf("%d", &t);
        
        if (t == 0)
        {
            printf("%d\n", group);
            continue;
        }
        
        int p;
        i64 d;
        scanf("%d %lld", &p, &d);
        
        v[--p] += d;
        
        if (v[p] <= l)
            continue;
        
        if (check[p] == 1)
            continue;
            
        check[p] = 1;
        bool left = false, right = false;
        
        if (p-1 >= 0)
            if (check[p-1] == 1)
                left = true;
        if (p+1 < n)
            if (check[p+1] == 1)
                right = true;
        
        if (!left && !right)
            group++;
        else if (left && right)
            group--;
        
    }
    
    return 0;
}

 

 

ㅋㅋㅋㅋㅋ

ㅋㅋ

여러번 틀렸다

 

처음에는 배열 범위 벗어나서 틀리고 그 다음은 출력 이상하게 해서 틀리고 (왜그랬지)

 

마지막은 이거 이미 l보다 긴 머리 또 길 때 예외처리 안 해서 틀렸다!

 

예외 찾았을 때 놀랬음ㅋㅋㅋ 이걸 빠트렸구나 

 

암튼 풀다보니 괜찮은 문제였다