Lesson 16. Gready algorithm - TieRopes

1. 문제

There are N ropes numbered from 0 to N − 1, whose lengths are given in an array A, lying on the floor in a line. For each I (0 ≤ I < N), the length of rope I on the line is A[I].
We say that two ropes I and I + 1 are adjacent. Two adjacent ropes can be tied together with a knot, and the length of the tied rope is the sum of lengths of both ropes. The resulting new rope can then be tied again.
For a given integer K, the goal is to tie the ropes in such a way that the number of ropes whose length is greater than or equal to K is maximal.

For example, consider K = 4 and array A such that:
A[0] = 1
A[1] = 2
A[2] = 3
A[3] = 4
A[4] = 1
A[5] = 1
A[6] = 3

The ropes are shown in the figure below.

We can tie:
  - rope 1 with rope 2 to produce a rope of length A[1] + A[2] = 5;
  - rope 4 with rope 5 with rope 6 to produce a rope of length A[4] + A[5] + A[6] = 5.

After that, there will be three ropes whose lengths are greater than or equal to K = 4. It is not possible to produce four such ropes.

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

that, given an integer K and a non-empty array A of N integers, returns the maximum number of ropes of length greater than or equal to K that can be created.

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

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

 

K길이 보다 길거나 같은 로프의 개수 구하는 문제. (인접한 로프는 묶을 수 있다)

 

주어진 로프(A)

인접한 로프(A[i], A[i+1])

 

예시) K = 4, return 3

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]
1	2	3	4	1	1	3

 

A[1] + A[2] = 5

A[4] + A[5] + A[6] = 5

길이가 4 이상인 로프의 개수는, 3개 

 

2. 매개변수 조건

• Vector A 크기: 1 ~ 100,000
• Vector A 요소: 1 ~ 1,000,000,000
• K: 1 ~ 1,000,000,000

 

3. 문제풀이 전략

그리디 알고리즘, 그리디 알고리즘이란? 매 순간 당장 최적인 답을 선택하는 알고리즘.

주의할점은 매 순간 최적이, 종합적으로도 최적이라는 보장은 없다. 따라서 그리디 알고리즘은 항상 최적의 해를 도출하지는 못한다.

 

이 문제에서 그리디 알고리즘은 '가능한 한 많은 로프를 K 이상으로 만들기 위해 로프를 최소한으로 사용한다' 이다.

따라서 현재 위치에서 시작하여 가능한 최소의 로프로 K 이상을 만드는 것이 최적해의 일부가 된다. (이 방법이 최적해의 일부가 되는 이유는 각 로프는 한번씩만 사용되기(인접한 로프만 묶을 수 있기) 때문이다. 

 

4. 코드 (C++)

0번째부터 순차적으로 로프를 묶어서 길이가 K 이상인 로프를 만든다.

int solution(int K, vector<int> &A) {

    int len = 0;
    int cnt = 0;

    for(size_t i = 0; i < A.size(); i++)
    {
        len += A[i];
        if(len >= K)
        {
            cnt++;
            len = 0;
        }
    }

    return cnt;
}

 

5. 결과