https://programmers.co.kr/learn/courses/30/lessons/12927

  • flow
    처음에 생각을 짧게 해서 (Sum % leng) * (Sum//leng + 1)^2 + (leng - Sum % leng) * (Sum//leng)^2 이런 공식 (sum == sum(works)-n, leng == len(works)) 이 적용되나 했는데 n이 작고 works 간 element 값들의 차이가 크면 당연히 틀리게 되서 ㅋㅋ 그러한 예외케이스에 매몰되다 보니 다음 코드도 되게 비효율적이게 짜게 되었다. 어떤 방법이었냐면 works를 reverse sort 해놓고 첫번째 element와 두번째 element 간 차이만큼 빼면서 위치 바꾸고 나아가는 방법이었다..
    def solution(n, works):
      answer = 0
      works.sort(reverse=True)
      while n > 0:
        if len(works) == 1:
            if n > works[0]:
                works.pop(0)
                break
            else:
                works[0] -= n
                n = 0
        if n < works[0]-works[1]+1:
            works[0] -= n
            n = 0
        else:
            cur = works[1]-1
            n -= (works[0]-works[1]+1)
            if cur == 0:
                works.pop(0)
            else:
                for j in range(1,len(works)):
                    if works[j] > cur:
                        works[j-1] = works[j]
                        if j == len(works)-1:
                            works[j] = cur
                    else:
                        works[j-1] = cur
                        break
      for k in range(len(works)):
          answer += works[k]**2
      return answer

지금 보면 단순히 (10001,10000,1) n=5000 같은 케이스만 와도 엄청 비효율적이게 동작하는 것이 보인다.;;
뭐 암튼 아니다 싶어서 다 지우고 좀 더 생각해봤는데 제법 간단하게 이분 탐색법이 적용될 수 있다는 것을 깨달았다.. 그 이후론 쉬운 내용이라 패스..