현재 사용할 수 있는 향료 중에서 탑노트, 미들노트, 베이스노트에 하나씩 배치한다고 하자.

각 향료의 향도를 각각 a, b, c라고 하면, 만들어진 향수가 조건을 만족하려면 다음 식이 성립해야 한다.

a + b + c >= K

세 향료를 모두 직접 선택하면 가능한 모든 경우를 확인해야 하므로 시간 복잡도는 O(M³)이다. 여기서 M은 현재 사용 가능한 향료의 개수다.

이를 줄이기 위해 탑노트와 미들노트를 먼저 고정한다.

a + b + c >= K

위 식을 c에 대해 정리하면 다음과 같다.

c >= K - a - b

즉, 탑노트 a와 미들노트 b를 선택한 뒤에는 향도가 K - a - b 이상인 베이스노트가 몇 개인지만 구하면 된다.

정렬과 lower_bound 활용

먼저 현재 사용 가능한 향료들의 향도를 오름차순으로 정렬한다.

sort(active.begin(), active.end());

정렬된 배열에서는 lower_bound()를 사용해 특정 값 이상인 첫 번째 원소의 위치를 빠르게 찾을 수 있다.

long long answer = 0;

for (int top : active) {
    for (int middle : active) {
        long long target = K - top - middle;

        auto it = lower_bound(
            active.begin(),
            active.end(),
            target
        );

        answer += active.end() - it;
    }
}

target은 베이스노트가 가져야 하는 최소 향도다.

long long target = K - top - middle;

그리고 다음 코드는 정렬된 active에서 target 이상인 첫 번째 원소의 위치를 찾는다.

auto it = lower_bound(
    active.begin(),
    active.end(),
    target
);

it부터 active.end() 직전까지의 모든 향료는 target 이상이므로 베이스노트로 사용할 수 있다.

따라서 가능한 베이스노트의 개수는 다음과 같다.

active.end() - it

이 값을 모든 탑노트와 미들노트 선택에 대해 더하면 조건을 만족하는 전체 향수 구성의 개수를 구할 수 있다.

예시

현재 향료의 향도가 다음과 같다고 하자.

active = {2, 4, 5}
K = 10

탑노트로 2, 미들노트로 4를 선택하면 베이스노트는 다음 조건을 만족해야 한다.

2 + 4 + c >= 10
c >= 4

정렬된 배열 {2, 4, 5}에서 4 이상인 값은 다음 두 개다.

4, 5

따라서 이 경우 가능한 베이스노트는 2개다.

auto it = lower_bound(active.begin(), active.end(), 4);

answer += active.end() - it;  // 2

순서와 중복에 주의하기

탑노트, 미들노트, 베이스노트는 서로 다른 자리이므로 배치 순서가 중요하다.

(2, 4, 5)
(4, 2, 5)

위 두 경우는 서로 다른 향수 구성이다. 따라서 탑노트와 미들노트를 각각 전체 향료에서 독립적으로 선택해야 한다.

for (int top : active) {
    for (int middle : active) {

또한 같은 번호의 향료를 여러 자리에 사용할 수 있으므로, 한 번 선택한 향료를 배열에서 제외하면 안 된다.

서로 다른 번호의 향료가 같은 향도를 가질 수도 있다. 향도가 같더라도 번호가 다르면 서로 다른 선택이므로, 향수 구성에서는 중복된 향도를 제거하면 안 된다.

sort(active.begin(), active.end());  // 정렬만 수행

다음과 같이 unique()로 중복을 제거하면 경우의 수가 잘못 계산된다.

// 향수 구성에서는 사용하면 안 됨
active.erase(
    unique(active.begin(), active.end()),
    active.end()
);

시간 복잡도

세 향료를 모두 직접 선택하면:

O(M³)

탑노트와 미들노트만 직접 선택하고, 베이스노트는 lower_bound()로 찾으면:

탑노트 선택: M
미들노트 선택: M
이분 탐색: log M

따라서 전체 시간 복잡도는 다음과 같다.

O(M² log M)

경우의 수는 최대 M³까지 커질 수 있으므로 정답은 int가 아닌 long long으로 저장해야 한다.

long long answer = 0;

핵심 정리

세 수의 합 조건에서는 두 수를 먼저 고정한 뒤, 남은 한 수가 만족해야 하는 최소값을 계산할 수 있다. 배열을 정렬해 두면 그 최소값 이상인 원소의 개수를 lower_bound()로 빠르게 구할 수 있다.

a + b + c >= K
c >= K - a - b

auto it = lower_bound(
    active.begin(),
    active.end(),
    K - top - middle
);

answer += active.end() - it;