끄적끄적

문제풀이

 works의 요소들의 제곱의 합이 가장 작게 하면 되는 문제로, works 요소들에서 주어진 n만큼을 적절히 빼서 works의 요소들의 최댓값을 가장 작게 만들어주면 된다. 따라서 가장 단순한 풀이로는, works를 정렬해가며 최댓값인 요소에서 1씩 빼는 과정을 n번 반복하면 된다. 

 하지만 위와 같은 방법으로 풀게되면, 당연히 효율이 좋지 못하므로, 더 효율적인 풀이를 고려해야한다. 제 풀이는 다음과 같습니다.

 1. works를 정렬한 후, i를 1씩 늘려가며 works의 i-1번째 요소까지의 모든 요소들의 값을 같게 하는데,

 1-1. 만약 works의 0번째부터 i-1번째 요소들을 모두 i번째 요소와 같도록 만들 수 있다면 바꾼 후, 바꿔준 만큼 n에서 빼줍니다.

 1-2. 불가능하다면 1과정을 멈춘다.

 2. 1-1을 거쳐 값을 똑같이 맞춰줄 수 있었던 요소들에 대하여 남은 n을 공평하게 배분한다.

 3. 남은 값들을 앞에서부터 1씩 배분한다.

예시

 works = [3,5,7], n = 3인 경우를 예로 들어보면 다음과 같다.

알고리즘이 동작하는 과정을 편의상 t라고 했습니다. 

t=0은 과정 1의 정렬을 하는 과정입니다.

t=1은 works의 두번째 요소(works[1])까지의 요소들의 값들이 같도록 만드는 과정입니다. works[0]을  works[1]과 같도록 만들 수 있으므로 바꾸어주고 n에서 works[0]-works[1]을 빼줍니다. i가 2 이상이라면 i*(works[i-1]-works[i])를 빼주면 됩니다. 

t=2는 과정 2인데, 0이 아닌 요소가 3개인데, n은 1이므로 이 과정은 진행되지 않지만, 이해를 돕기위해 넣었습니다.

t=3은 과정 3으로, 남아있는 n을 앞에서부터 1씩 처리하는 과정입니다.

이제 t=3에서의 요소의 값들을 제곱하여 반환하면 됩니다.

* 시간복잡도는 최악의 경우 for문 3번으로 끝나므로, works의 길이를 N이라 하면 O(NlonN + N)이 됩니다(정확히는 O(NlonN + 3N)).

Python Code

line 6의 for문이 과정 1(equal index까지 요소들의 값이 같게 됩니다.),

line 19이 n을 공평하게 처리하는 부분,

line 23이 남은 n을 1씩 앞에서부터 처리하는 부분입니다.

문제링크