[programmers-lv2] 서버 증설 횟수

[programmers-lv2] 서버 증설 횟수

🙋‍♂️ 들어가며

이번 문제에서는 현재 가동중인 서버 현황을 잘 확인하고, 최소한의 전력을 사용하는게 핵심이다.

test case 1번 기준으로 작성했다

m = 3;
k = 5;

이런식으로 풀면 되겠다.

준비한 것은 2개의 풀이다.

2중 반복문

그리고

1중 반복문인 DP다

코드는 다음과 같다

✅ 2중 반복문

class Solution {
    public int solution(int[] players, int m, int k) {
        int min_cnt = 0;
        
        int[] cur_server = new int[24];
        // 1. 현재 서버 검사
        for (int i = 0; i < 24; i++) {
            int cur_mod = players[i] / m;
            
            // 2. 만약 현재 서버가 충분하다면 pass
            if (cur_server[i] >= cur_mod) continue;
            
            // 3. 그렇지 못하다면 서버에 차이만큼 추가
            int diff = cur_mod - cur_server[i];
            
            for (int j = i; j < i + k; j++) {
                // 3-1. 범위 넘어가면 멈춤
                if (j >= 24) break;
                
                // 3-2. 차이만큼 서버에 추가
                cur_server[j] += diff;
            }
            
            // 4. 횟수에 추가
            min_cnt += diff;
            
            
        }
        
        return min_cnt;
    }
}

메모리, 수행시간을 절약하기 위해 누적합 DP를 사용해야겠다

✅ 1중 반복문 DP

class Solution {
    public int solution(int[] players, int m, int k) {
        int time = 24;
        
        // 누적합용 DP
        int[] DP = new int[time];
        
        for (int t = 0; t < time; t++) {
            // 1. 누적합은 항상 갱신
            if (t > 0) {
                DP[t] = DP[t-1];
            }
            
            // 2. 마지막으로 서버를 켰을 수도 있고, 켜지 않았을 수도 있을때, 누적 몇개인지?
            int last_lighted_server_cum_cnt = 0;
            if (t >= k) {
                last_lighted_server_cum_cnt = DP[t-k];
            }
            
            // 3. 현재 구동중인 서버수
            int cur_running_server = DP[t] - last_lighted_server_cum_cnt;
            
            // 4. 필요한 서버수
            int req_server = players[t] / m;
            
            // 5. 만약에 서버수가 모자라다면?
            if (cur_running_server < req_server) {
                int diff = req_server - cur_running_server;
                DP[t] += diff;
            }
            
        }
        
        return DP[time-1];
    }
}