https://www.acmicpc.net/problem/1059
1059번: 좋은 구간
[9, 10], [9, 11], [9, 12], [10, 11], [10, 12]
www.acmicpc.net
접근
설명이 다소 난해하다... N을 포함하는 범위를 만들되, 그 범위 안에 집합의 원소가 속하면 안된다.
만약 N이 집합의 원소로 존재하면 어떻게 해서든지 문제의 조건을 만족할 수 없어서 0을 출력한다.
예를 들어 N을 5라고 하고 집합 S의 원소들을 {3, 1, 10, 8}이라고 할 때 집합의 원소들을 포함하지 않으면서 N을 포함하는 범위를 만들면 [4, 5], [4, 6], [4, 7], [5, 6], [5, 7]이 된다.
그러려면 N보다 작은 집합의 원소들 중 제일 큰 값(A)과 N보다 큰 집합의 원소들 중 제일 작은 값(B)을 구한 다음 A와 B사이에 있는 정수들을 구간으로 설정하면 된다.
이렇게 하면 다른 원소들은 포함하지 않고 순수하게 N만 포함하는 구간이 나타난다.
범위의 개수를 구하려면 N보다 같거나 작은 수의 개수 * N보다 같거나 큰 수의 개수를 구하면 된다.
A가 3, B가 9일 때 이 범위 안에서 N보다 같거나 작은 수가 3개고 N보다 같거나 큰 수가 3개다.
따라서 주황색 동그라미 개수 * 파란색 동그라미 개수가 이 문제의 답인데, [6, 6]같은 경우는 없어야 한다. 문제에서 구간을 나타내는 값은 서로 같지 않다고 하기 때문이다.
그래서 [N, N]으로 이루어진 범위는 빼기 위해 구한 값에서 1을 뺀다.
#include <iostream>
int main() {
int A, B, L, S[50], N;
scanf("%d", &L);
for (int i = 0; i < L; i++) {
scanf("%d", &S[i]);
}
scanf("%d", &N);
int below = 0, above = 1000;
for (int i = 0; i < L; i++) {
if (S[i] > N) {
above = above > S[i] ? S[i] : above;
} else if (S[i] < N) {
below = below < S[i] ? S[i] : below;
} else {
printf("0");
return 0;
}
}
printf("%d", (N - below) * (above - N) - 1);
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
6600 원의 둘레 (1) | 2022.09.23 |
---|---|
1500 최대 곱 (1) | 2022.09.20 |
9465 스티커 (0) | 2022.09.10 |
2502 떡 먹는 호랑이 (0) | 2022.09.07 |
1876 튕기는 볼링공 (0) | 2022.09.06 |
댓글