[프로그래머스] 서버 증설

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define long long size_t
using namespace std;

int solution(int players[], size_t players_len, int m, int k) {
    int answer = 0;
    int server[1000] = {0}; // 충분한 크기 가정

    for (size_t i = 0; i < players_len; i++) {
        int capacity = server[i] * m + (m - 1);

        if (players[i] > capacity) {
            int need = players[i] - capacity;
            int extra = (need + m - 1) / m; // 올림 처리

            for (int j = 0; j < k; j++) {
                server[i + j] += extra;
            }

            answer += extra;
        }
    }

    return answer;
}

<설명>

사람이 m명 증가 시 서버 1대가 추가로 필요함: nxm명 이상 (n+1)xm명 미만이면 n대의 서버가 운영 중이어야 함

한번 증설되면 k시간 동안 운영하고 반납함 (k=5일 때 10시에 증설한 서버는 10~15시에만 운영됨)

하루동안 모든 이용자가 게임하기 위해 서버는 최소 몇 번 증설해야하나?

 

[변수]

players: 시간대별 게임 이용자의 수 / 길이: 24, 크기 <=1000

m: 서버 한 대로 감당할 수 있는 최대 이용자의 수 / <=1000

k: 서버 한 대가 운영 가능한 시간 / <=24

 

[풀이]

players[i]는 i 시간동안 유입되는 사용자 수

server[i] * m + (m - 1)가 처리 가능한 최대 사용자 수 (1만 더 초과해도 서버 1대를 추가해야 함)

players[i] > capacity는 현재 서버 수로 i 시간의 플레이어 수를 감당 못하면..

int extra = (need + m - 1) / m;는 부족한 인원을 감당하기 위해 서버 몇 대가 더 필요한지 (정수 나눗셈 올림)..

for (int j = 0; j < k; j++) {

server[i + j] += extra;

}는 새로 추가한 서버는 i시간부터 k시간 동안 유지되어야 함

 

<참고>

https://velog.io/@sanghee0820/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-389479-%EC%84%9C%EB%B2%84-%EC%A6%9D%EC%84%A4-%ED%9A%9F%EC%88%98