[ Lv 3 ] 야근 지수

풀이 과정

1. works를 내림차순으로 정렬한다(작업량 순)
2. 거듭제곱의 합을 최소로 하려면 가장 큰 작업량부터 줄여야 한다.
   • 따라서, 가장 큰 작업량을 기준으로 1씩 빼주면서.
   • 각 작업들을 루프돌면서 현재 작업량보다 크다면 1을 빼주고, 작다면 바로 종료(내림차순으로 정렬하였으므로 아래는 모두 작음), 평탄화한다고 생각하면 됨.
   • 이 과정을 총 빼준 값이 n이 될때까지 하면 된다.

     

3. answer 전체를 제곱후 더하면 된다.

---

소스 코드

from collections import deque

def solution(n, works):
    answer = 0
    cut = 0
    flag = False
    works.sort(reverse=True)
    m_height = works[0]
    for height in range(m_height, 0, -1): 
    # 작업량을 높이로 두고 한층씩 잘라가면서 생각
        for i in range(len(works)):
            if works[i] == height:
                cut += 1
                works[i] -= 1
                if cut == n: # n개 자르면 종료
                    flag = True
                    break
            else: 
                # 내림차순 정렬했으므로 높이보다 작아지면 바로 break
                break
        if flag:
            break

    for work in works:
        answer += work * work

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges