야근 지수

야근 지수
회사원인 수민이는 많은 일이 쌓여 있습니다. 수민이는 야근을 최소화하기 위해 남은 일의 작업량을 숫자로 메기고, 일에 대한 야근 지수를 줄이기로 결정했습니다. 야근 지수는 남은 일의 작업량을 제곱하여 더한 값을 의미합니다. 수민이는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 수민이의 퇴근까지 남은 N 시간과 각 일에 대한 작업량이 있을 때, noOvertime 함수를 제작하여 수민이의 야근 지수를 최소화 한 결과를 출력해 주세요. 예를 들어, N=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 야근 지수는 22 + 22 + 22 = 12가 되어 12를 반환해 줍니다.

dp로 풀려고 생각해서 n-1시간의 최소 야근지수 D[n-1]에서 각 요소들을 1씩 빼준 야근지수의 최소값이 D[n]이 된다고 생각했다. 즉 D[n] = Min(D[n-1](a-1, b, c...), D[n-1](a, b-1, c...) D[n-1](a, b, c-1, ...), ...) 이런 식이다. 

그런데 이렇게 해결하려고 하니 D[n]이 배열 형태라 점화식이 생각보다 깔끔하게 안나와서 횟수를 줄여주는 방법으로 바꿨다. (원리는 같다.) 그래서 조금 지저분한 코드가 나왔는데...

class NoOvertime {
    int dp[] = new int[10000000];
    
    public int nightShift(int[] works) {
        int result = 0;
        for(int i = 0; i<works.length;i++) {
            result+= (int) Math.pow(works[i], 2);
        }
        return result;
    }
    
    public int noOvertime(int no, int[] works) {
        int min;
        int temp[] = new int[works.length];
        
        works[0]-=1;
        min = nightShift(works);
        System.arraycopy(works, 0, temp, 0, works.length);
        works[0]+=1;
        
        for(int i = 1; i< works.length;i++) {
            works[i]-=1;
            if(min >= nightShift(works)) {
                min = nightShift(works);
                System.arraycopy(works, 0, temp, 0, works.length);
            } 
            works[i]+=1;
        }
        
        if(no > 1) {
            return noOvertime(no-1, temp);
        } else {
            return min;
        }
    }
    public static void main(String[] args) {
        NoOvertime c = new NoOvertime();
        int []test = {4,3,3};
        System.out.println(c.noOvertime(4,test));
    }
}
 

풀고나서 검색해보니 이 문제는 "최소자승합"이라는 용어를 가진 문제였다. 직관적으로 생각했을 때 "가장 큰 수를 찾아서 1을 빼주면 제곱의 합은 최소가 된다."라는 개념을 찾아내는 문제인 것이다. 아니... 이러면 머리 싸맨 시간이 뭐가 됩니까... ㅜㅜ

여담으로 배열의 값을 복사하는 System.arraycopy라는 메소드를 배울 수 있었다. 시스템 메소드라서 자주 사용하진 말아야겠다.