[Codility] Lesson16 - Greedy algorithms: TieRopes

Problem

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:

class Solution { public int solution(int K, 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].

  Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

How to solve

- 구해야 하는것?

로프의 길이를 원소로 하는 배열 A와 길이 K가 주어질 때, 

인접한 로프를 더해서 길이 K 이상의 로프를 만들 때, 만들 수 있는 최대 로프의 수 구하기!

즉, 인접한 배열의 숫자를 더해서 K이상의 숫자를 만들 때, 만들 수 있는 K이상의 수 구하기

 

- 풀이

1. 로프 길이, 만들 수 있는 로프 수 초기화

   rope_len = 0

   count = 0

2. 배열 A를 index 0부터 시작해서 길이 K이상이 될 때까지 더한다.

   K이상이 되면 로프 수 count 를 1 증가 시킨다. 

   로프 길이를 0으로 초기화한다. 

   for(int i=0; i<len; i++){

        rope_len +=A[i];

        if(rope_len >= K){

            count++;

            rope_len = 0;

        }

   }

3. count 를 return 한다. 

Solution(c++)

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(int K, vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int len = A.size();
    int rope_len = 0;
    int count = 0;

    for(int i=0; i<len; i++){
        rope_len +=A[i];
        if(rope_len >= K){
            count++;
            rope_len = 0;
        }
    }
    return count;
}

Test Result

app.codility.com/demo/results/training56QFPW-3H5/

Test results - Codility