Determine the Minimum Sum of a k-avoiding Array[M,Math,Greedy]

https://leetcode.com/problems/determine-the-minimum-sum-of-a-k-avoiding-array/description/

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

 

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.

Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.

 

Constraints:

• 1 <= n, k <= 50

 

1. Python

class Solution:
    def minimumSum(self, n: int, k: int) -> int:
 
        lst = []
        i = 1
        while len(lst) < n :
            cnt = 0
            for x in lst :
                if x+i != k :
                    cnt+=1
            if cnt == len(lst):
                lst.append(i)
            i+=1
        return sum(lst)

나의 코드이건만.. Runtime은 꼴등이다 ㅠ

 

2. C

int minimumSum(int n, int k){
    int arr[50];
    int a = 1;
    int lst_size = 0;
    int sum = 0;
    while(lst_size < n){
        int cnt = 0;    
        for(int i=0;i<lst_size;i++){
            if(arr[i]+a != k){
                cnt++;}
        }
        if(cnt == lst_size){
            arr[lst_size] = a;
            lst_size++;
            sum+=a;
        }
        a++;
        }
    return sum;
}

C는 진짜 무능하다..

 

모든 것들을 다 일일이 변수로 만들어줘야 한다.

 

index, sum, length.. 이 모든 것들을 다 만들어 줘야 하는 무능의 극치.. 왜 배우나 싶다

 

저 condition 부분을 함수 helper를 써서 표현하면 좀 더 효과적이다.

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>



bool cond(int* arr,int size,int a,int k){
    for(int i=0;i<size;i++){
        if(arr[i]+a == k) return false;
    }
    return true;
}

int minimum(int n, int k){

    int arr[50];
    int size = 0;
    int a = 1;
    int sum = 0;

    while(size < n){

        if(cond(arr,size,a,k)){
            arr[size++] = a;
            sum+=a;
        }
        a ++;
    }

    return sum;
}





int main(void){
    // int a = max(3,5);
    // printf("%d\n",a);

    int n1 = 5, k1 = 4;
    printf("Minimum sum for n = %d, k = %d is %d\n", n1, k1, minimum(n1, k1));

    return 0;
}

 

 

3. C++

 

class Solution {
public:
    int minimumSum(int n, int k) {
        vector<int> vec;
        int a = 1;
        int sum = 0;
        while(vec.size() < n ){
            int cnt = 0;
            for(int i=0;i<vec.size();i++){
                if(vec[i]+a != k) cnt++;
            }
            if(cnt==vec.size()){
                vec.push_back(a);
                sum+=a;
            }
            a++;
        }
        return sum;
    }
};