[파이썬] 프로그래머스 Level.3 | 탐욕법(greedy) | 저울

문제 설명

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있습니다.

저울추가 담긴 배열 weight가 매개변수로 주어질 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요.

예를 들어, 무게가 각각 [3, 1, 6, 2, 7, 30, 1]인 7개의 저울추를 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21입니다.

 

제한 사항

• 저울추의 개수는 1개 이상 10,000개 이하입니다.

• 각 추의 무게는 1 이상 1,000,000 이하입니다.

 

---

풀이

 

처음에 단순히 떠올린 풀이는 제한사항이 있었기 때문에 완전탐색을 이용한 풀이였다.

 

def sol2(num,weight):
    answer2=0
    length=len(weight)
    for j in range(0,len(weight)):
        if num>=weight[j]:
            num-=weight[j]
        if num==0:
            answer2=0
        else:
            answer2=1
    return answer2
    
def solution(weight):
    answer = 0
    weight=sorted(weight,reverse=True)
    for i in range(1,1000000):
        
        if sol2(i,weight)==1:
            print(i)
            answer=i
            break
    
    return answer

그러나 이는 런타임 에러를 일으켰다. 

완전탐색이 틀린 풀이는 아니지만 탐욕법 카테고리 안에서 완전탐색을 이용하는 것은 런타임에러를 불어일으키는 것이 어쩌면 당연했다.

 

따라서 탐욕법을 이용한 풀이도 다시 코드를 짰다. 

def solution(weight):
    answer=0
    weight=sorted(weight)
    weight2=[]
    weight2.append(weight[0])
    
    for i in range(1,len(weight)): #누적합 생성 
        temp=weight[i]+weight2[i-1]
        weight2.append(temp)
        
    if weight[0]!=1:
        return 1
 
    for num in range(1,len(weight)-1):
        if weight2[num]+1<weight[num+1]:
            answer=weight2[num]+1
            return answer
            break
    if answer==0:
        answer=weight2[len(weight2)-1]+1
        return answer

이 풀이는 탐욕법에 대한 이해 보다는 수학적 이해를 바탕으로 풀어야하는 문제인 것 같다. 

누적합을 나타낸 배열 weight2를 만들고,

weight2[i]+1 < weight[i+1] 인 지점의 weight2[i]+1 값이 answer가 되는데,

 

여기서 주의해야 할 점은 2가지가 있다.

첫째, [3,4,5] 와 같은 배열의 답은 당연히 1이 되어야 한다는 점.

둘째, [1,1,3] 와 같은 배열의 경우, 누적합 배열 : [1,2,5] 인데 이 경우, weight2[2]=5와 비교할 weight[3]의 원소가 없기 때문에 원소 끝까지 비교했는데 answer가 안나올 경우, 누적합 배열의 마지막 원소+1 이 answer가 되도록 해야 한다.

 

그래서 이 두 가지 경우를 위해 if 문을 이용하여 처리를 해주었다.