Lesson 15. Caterpillar method - CountTriangles

1. 문제

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
  - A[P] + A[Q] > A[R],
  - A[Q] + A[R] > A[P],
  - A[R] + A[P] > A[Q].

For example, consider array A such that:
A[0] = 10
A[1] = 2
A[2] = 5
A[3] = 1
A[4] = 8
A[5] = 12

There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5).

Write a function:
  int solution(vector<int> &A);

that, given an array A consisting of N integers, returns the number of triangular triplets in this array.

For example, given array A such that:
A[0] = 10
A[1] = 2
A[2] = 5
A[3] = 1
A[4] = 8
A[5] = 12
the function should return 4, as explained above.

Write an efficient algorithm for the following assumptions:
  - N is an integer within the range [0..1,000];
  - each element of array A is an integer within the range [1..1,000,000,000].

 

다음 조건을 만족하는 삼각형의 개수 구하기

• 0 ≤ P < Q < R < N
• A[P] + A[Q] > A[R]
• A[Q] + A[R] > A[P]
• A[R] + A[P] > A[Q]

예시) return 4

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]
10	2	5	1	8	12

 

만들어지는 삼각형:

(A[0], A[2], A[4]),

(A[0], A[2], A[5]),

(A[0], A[4], A[5]),

(A[2], A[4], A[5])

 

2. 매개변수 조건

Vector A 크기: 0 ~ 1,000

Vector A 요소 값 범위: 1 ~ 1,000,000,000

 

 

3. 코드 (C++)

이전에 풀었던 Lesson 6. Sorting - Triangle 문제와 매우 유사하다.

문제를 읽고, 주어진 A의 요소 순서가 지켜질 필요가 없다는 사실만 인지할 수 있다면, 어렵지 않다.

P, Q, R 조건은 같은 인덱스를 사용할 수 없다는 뜻이지, Vector A의 값 순서가 지켜져야 한다는 뜻이 아니다.

따라서 정렬을 이용해서, 반복횟수를 줄이면, 100% 결과를 달성할 수 있다.

#include <algorithm>

int solution(vector<int> &A) {

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

    //for(const auto v : A) cout << v << ' '; cout << endl;

    int cnt = 0;

    for(int P = 0; P < (int)A.size(); P++)
    {
        for(int Q = P + 1; Q < (int)A.size(); Q++)
        {
            for(int R = Q + 1; R < (int)A.size(); R++)
            {
                if(A[P] + A[Q] > A[R])
                    cnt++;
                else // 정렬되어 있으므로, 더 진행할 필요가 없다
                    break;
            }
        }
    }

    return cnt;
}

 

 

4. 결과