ABC 247 - E. Max Min

gim-hangil·2022년 4월 13일
0

문제 풀이

목록 보기
5/7

지금 풀어보기

📝 문제 읽기

길이가 N인 수열 A가 주어진다. AL, AL+1, ... , AR의 최솟값이 X이고 최댓값이 Y인 정수쌍 [L, R]의 갯수를 구하라.

💡 전략 수립

앳코더의 에디토리얼을 참고했습니다. 앳코더 영문 에디토리얼

[L, R]에 X보다 크거나 Y보다 작은 수가 포함되어 있으면 조건을 만족할 수 없다. 문제를 단순화하기 위해 X와 Y 사이에 있는 수로만 이루어진 수열을 가정해보자. 실제 문제에서는 범위 밖의 수가 나오면 수열을 자르는 방식으로 단순화된 작은 문제의 모음으로 바꿀 수 있다.

그렇다면 최댓값이 X이고, 최솟값이 Y인 부분수열의 갯수는, X와 Y를 모두 포함하는 범위의 갯수로 바꿀 수 있다.

단순화된 문제

최댓값이 X이고, 최솟값이 Y인 수열 B가 주어질 때, X와 Y를 모두 포함하는 부분수열의 갯수는?

이제 슬라이딩 윈도우로 이 문제를 해결할 수 있다.

  1. L = 1, R = 1로 시작한다.
  2. [L, R]이 조건을 만족하지 못하면 R을 1 증가시킨다.
  3. [L, R]이 조건을 만족하면 R보다 큰 x에 대해 [L, x]도 조건을 만족하므로 그만큼 갯수를 추가하고, L을 1 늘린다.

가능한 각 L에 대해 조건을 만족하는 R의 갯수를 더하여 문제가 해결된다.

이 과정은 수열의 길이 B에 대해 O(B)에 해결되고, 자른 부분수열을 모두 이은 수열은 길이가 N보다 작거나 같기 때문에 전체 문제는 O(N)에 해결할 수 있다.

✨ 구현

먼저 전략 수립 단계에서 말로 설명하고 넘겼던 가정인, X와 Y 사이의 수만 있는 수열로 나누어 해법을 적용해야 한다.

ll solution() {
	ll cnt = 0, l = 0, r = 0;
    while (l < n) {
    	// [l, r] 범위에 X와 Y 사이의 수만 있도록 업데이트
        cnt += partial_solution(l, r);
        l = r + 1;
	}
    return cnt;
}

범위 안의 수만 있는 [l, r]을 찾아야 하는데, 이렇게 구할 수 있다.

while (l < n && (x < arr[l] || arr[l] < y)) l++; // 조건에 맞지 않으면 +1
r = l;
while (r < n && (y <= arr[r] && arr[r] <= x)) r++; // 조건에 맞으면 +1
r--;  // partial_solution이 범위를 inclusive range로 받을 것이므로...

그럼 [l, r]에 대해 부분해를 구하는 함수만 만들면 쉽게 해결된다.

ll partial_solution(ll from, ll to) {
	if (from >= n || to >= n) return 0;
    ll cnt = 0, l = from, r = from;
    while (true) {
    	if (match_condition(l, r)) {
        	cnt += to - r + 1;
            l++;
        } else {
        	r++;
            if (r > to) break;
        }
	}
}

여기서 X와 Y를 포함하는 범위인지를 확인하는 match_condition(l, r) 부분을 l부터 r까지 순회하며 확인하는 방법도 있지만, 간단히 범위 안에 있는 X와 Y 갯수를 저장하여 아래와 같이 바로 풀 수도 있다. 아이디어는 l이 오른쪽으로 가면 갯수가 줄어들거나 그대로이고, r이 오른쪽으로 가면 갯수가 늘어나거나 그대로라는 점이다.

ll partial_solution(ll from, ll to) {
	if (from >= n || to >= n) return 0;
    ll cnt = 0, l = from, r = from;
    while (true) {
    	if (has_x > 0 && has_y > 0) {
        	cnt += to - r + 1;
            l++;
            if (arr[l-1] == x) has_x--;
            if (arr[l-1] == y) has_y--;
        } else {
        	r++;
            if (r > to) break;
            if (arr[r] == x) has_x++;
            if (arr[r] == y) has_y++;
        }
	}
}

0개의 댓글