[ 프로그래머스 ] 야근 지수 파이썬python 풀이

 

// 문제 요약

 

야근을 하면 남은 일의 업무량을 제곱한 만큼 피로도가 쌓인다고 할때

 

남은 근무시간과 업무량이 리스트로 주어지면

 

최소의 야근 피로도는 얼마인가

 

 

 

// 풀이

 

효율성까지 따지는 이번 문제는 알고리즘으로는 힙 문제라고 할 수 있는데

 

단순히 힙 문제라고 하기엔 거의 모든 알고리즘 문제가 그러하듯

 

수학적 사고력 문제라고 할 수 있다.

 

우선 수학적 접근으로 이 문제를 보면

 

합이 일정한 수들의 제곱의 합이 최소가 되도록 하는 방법은 무엇인가?

 

라고 할 수 있다.

 

이런 간단한 문제들은 조금만 생각해 봐도 엄청 어렵다는 것을 알 수 있는데

 

제한 조건이 1개인 상황이어서 수가 3개 이상만 되어도

 

일반적인 제곱의 합을 단 하나의 매개변수에 대하여 알아내기가 불가능하기 때문이다.

 

그래도 감을 잡기 위해서 그림으로 한번 그려보자.

그림은 합친 길이가 같은 선분들을 이용해서 정사각형을 그렸을때

 

넓이의 차이가 얼마나 나는가를 보여준다.

 

보면 알겠지만 아무리 다른 값들을 작게 만들더라도

 

가장 큰 값이 다른 값에 비해 너무 커져버리면 의미가 없어진다.

 

뒤에 첨부해서 더 설명을 하겠지만 핵심적인 부분은 최대값과 최소값의 차이가 적은

 

그러니까 평균에 가까운 값들이 모여있을수록 제곱의 합은 더 작아진다.

 

못 믿을까봐 한번 보여주면

 

이렇게 가장 큰 사각형 하나도 다 채울 수가 없게 커져버린다.

 

그러니까 주어진 n을 가장 잘 분배해서 빼는데

 

빼고 난 결과의 분산이 가장 작도록 빼주면 된다.

 

 

 

나는 처음에 접근할때

sub_mean = ( sum(works) - n ) / len(works)

정도의 접근으로 이 sub_mean과 차이가 나는 만큼 works의 값들을 빼주고

 

또 그만큼 n 이 빠지도록 루프를 돌렸는데

 

이 경우 생각해보면 결과의 분산이 최소가 되도록 빼는 과정이라고 할 수 없다.

 

n이 0이 되도록 뺀 후에도 어떤 값이 sub_mean 보다 한참 크다면 반례가 될 수 있다.

 

따라서 힙을 이용해서 풀어보도록 하자.

 

코드를 보자.

from heapq import heappop, heappush

def solution(n, works):
    if sum(works) <= n:
        return 0

    hq = []
    for work in works:
        heappush(hq, -work)

    while n:
        heappush(hq, (heappop(hq) + 1))
        n -= 1

    return sum([k ** 2 for k in hq])

힙을 이용하되 최소힙임을 감안하여

 

값을 넣을때 마이너스를 취해준 후 넣는다.

 

그리고 최대값을 꺼내서 1시간 일해준 처리를 하면 되는데

 

음수로 넣었으므로 1을 더해주고 다시 힙에 넣는다.

 

1시간 일을 했으므로 n을 1 빼준다.

 

이 과정은 과정을 반복할때마다 변경된 최대값을 반영해주어야하므로

 

힙을 사용하는것이 가장 효율적인 접근이다.

 

마지막은 제곱을 하므로 부호를 수정해 줄 필요없이 제곱하고 더하면 된다.

 

 

 

 

// 수식으로 보면

 

대단한건 아니고 가려운 부분을 수식으로 한번 시원하게 긁을 수 있는지 보자.

 

$$a + b = C\ (\ C\ is\ constant.\ )\tag{1}$$

$$y = a^{2} + b^{2}\tag{2}$$

 

라고 하고 a 를 b에 대해서 나타내면

 

$$y = b^{2} + C^{2} -2bC + b^{2}\tag{3}$$

 

이므로 y가 최소인 값을 찾아보면

 

b에 대하여 아래로 볼록하므로

 

$$\frac{dy}{db} = 4b - 2C\tag{4}$$

 

가 0이 되는 지점이라고 할 수 있다. 그러니까 

 

$$b = \frac{C}{2}\tag{5}$$

 

인 지점이므로 자연스럽게 a 도 C의 절반이 되어야 한다.

 

즉 이 경우는 C가 0이 아닌 경우 평균에 수렴해야한다는 것을 잘 알 수 있다.

 

그런데 항이 세개 이상이 되면 이런 접근을 못쓴다.

 

그래서 연역적 방식으로는 해볼 수 있는데

 

$$ d = \frac{a+b+c}{3} \tag{6}$$

$$a^{2} + b^{2} + c^{2} < 3d^{2}\ ? \tag{7}$$

 

6이라고 할때 7이 성립하는지 보자.

 

$$ d^{2} = \frac{a^{2} + b^{2} + c^{2} + 2ab + 2bc + 2ca}{9} \tag{8} $$

 

이므로 결국엔

 

$$a^{2} + b^{2} + c^{2} < ab + bc + ca\ ? \tag{9}$$

 

이게 성립하느냐 하는 것이다.

 

a=b=c 이면 반례가 나오고

 

a, b, c 중에서 어느 하나가 매우 작은 경우 부등호가 맞지 않게 된다.

 

따라서 적어도

 

$$a^{2} + b^{2} + c^{2}  \ge 3d^{2} \tag{10}$$

 

이렇게 성립하는 것이 맞다고 할 수 있다.

 

그러니까 합이 같은 수들의 제곱의 합은 그 수들이 평균에 가까울때 가장 작다고 말할 수 있다.

 

혹시 부족한 부분이 있으면 댓글로 지적해주기 바란다.