[Codility] TieRopes coding task ( Greedy algorithm) - Python 풀이

Task description

For a given array A of N integers and a sequence S of N integers from the set {−1, 1}, we define val(A, S) as follows:

val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|

(Assume that the sum of zero elements equals zero.)

For a given array A, we are looking for such a sequence S that minimizes val(A,S).

Write a function:

def solution(A)

that, given an array A of N integers, computes the minimum value of val(A,S) from all possible values of val(A,S) for all possible sequences S of N integers from the set {−1, 1}.

For example, given array:

A[0] = 1 A[1] = 5 A[2] = 2 A[3] = -2

your function should return 0, since for S = [−1, 1, −1, 1], val(A, S) = 0, which is the minimum possible value.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..20,000];
• each element of array A is an integer within the range [−100..100].

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

 

 

오랜시간 고민하다가 답지를 보게 됐다.

답지를 보고도 이해가 가는데 한참 걸렸다.

DP쪽은 전에도 약했는데 앞으로 문제를 꾸준히 풀면서 실력을 더 키워야 겠다.

아래는 코딜리티에서 공개한 코드를 참고하여 다시 써본 코드.  참고 : https://codility.com/media/train/solution-min-abs-sum.pdf

 

이해하기 쉽게 써보려 했으나 한번에 이해하기는 어려울 듯 하다.

 

 

def solution(A):
    N = len(A)
	
    A = [abs(a) for a in A] # A의 값들을 절대값 취한 list
    
	M = max(A) # list A 중 가장 절대값이 큰 값
    
    S = sum(A) # A 값들을 절대값취해 더한 값으로 val(A,S)의 max값이다.

    count = [0] * (M + 1) # 각 값들이 몇번씩 등장했는지에 대한 list (A의 값들은 절대값이 100보다 작기때문에 중복이 많을 확률이 높다.)
    for i in range(N):
        count[A[i]] += 1
        
        
    dp = [-1] * (S + 1) # dp[i] = 더해서 i값이 된 후 남은 수의 갯수(-1이면 A의 값들을 적절히 더해서 해당 수를 만들 수 없다는 의미, 0보다 크다면 만들 수 있다는 의미)
    dp[0] = 0 # 아직 아무것도 안 더한 상태
    
    
    for a in range(1, M + 1):
    
        if count[a] > 0: # a의 절대값이 A에 1번이상 등장했다면,
        
            for j in range(S):
            
                if dp[j] >= 0: # 이미 이전의 값들을 더해서 j가 될 수 있다면 a는 더해줄 필요가 없으니 a의 갯수만큼 남게 된다. 
                    dp[j] = count[a]
                elif (j >= a and dp[j - a] > 0): # sum이 j가 될 수 없다면(아직 알 수 없다면) sum이 j-a가 되는 값에 a를 더해주면 됨 즉 dp[j-a]보다 남는 수가 하나 적어짐
                    dp[j] = dp[j - a] - 1
                    
    result = S
    
    for i in range(S // 2 + 1):
        if dp[i] >= 0: # sum이 i가 될 수 있다면
            result = min(result, S - 2 * i) # 최대값 S에서 i를 두번 빼주면 됨(S는 이미 i를 한 번 더해준 상태이므로 한 번 빼줘야 원래대로 되고 또 한번 더 빼줘야 -i를 한 값이 된다.)
          
    return result