[Softeer] 21년 재직자 대회 예선 - 마이크로서버

문제

<배경>

<입력>

<출력>

각각의 테스트 케이스에 대해, 한 줄에 하나씩, 순서대로, 필요한 최소 마이크로서버의 수를 출력한다.

---

풀이

문제는 이해하기 쉬운데 막상 알고리즘을 찾으라면 어려운 문제이다.

 

먼저 입력 처리를 해준다.

여기서 입력받은 서비스들의 메모리 요구량은 정렬을 해서 저장한다.

t = int(input())
for i in range(t):
    n = int(input())
    task = list(map(int,input().split()))
    task.sort()
    
    start = 0
    end = n-1
    servers = 0

리스트에서 앞부분부터 참조하는 start와 뒷부분부터 참조하는 end를 만들었다.

그리고 서버의 개수를 저장할 변수 servers도 선언해줬다.

 

문제를 해결하기 위해,

각 마이크로서비스가 요구하는 메모리를 300, 301~599, 600, 601~900 구간으로 나눠서 생각해보자.

 

1. 601~900구간은 무조건 하나의 마이크로서버에 혼자 할당되어야한다.

입력을 받을 때 정렬을 했으므로 뒤에서부터 앞으로 순회하면서 600이 넘는 애들에 대해 처리를 해준다.

이 경우엔 서버의 개수(servers변수)를 하나 늘리기만 하면된다.

다만 모든 서비스가 601 이상일 수 있으므로 -1인덱스를 참조하는 일이 없도록 end>=start 조건을 추가했다.

    while end >= start and task[end] > 600: #600보다 큰 값이면 서버 추가
        servers += 1
        end -= 1

 

2. 300, 600의 요구메모리가 있는 서비스들은 300 + 600 = 900으로 정확히 가득 채울 수 있으므로 최대한 짝지어주는 것이 좋다.

이렇게 짝지었을 때는 300 또는 600짜리 서비스가 한쪽이 남을 가능성이 있다.

    while start < end and task[start] == 300 and task[end] ==600: #300과 600 세트처리
        servers += 1
        start += 1
        end -= 1

 

3. 300, 300, 300, 500, 500, 500 의 예시를 생각해보면 300이 남았다고 300짜리 3개를 묶어 먼저 900을 만들면 500짜리들이 모두 각각 서버에 배정되어야하고, 총 4개의 서버가 필요하다.

하지만 300+500 묶음으로 배정하면 총 3개의 서버로 가능해진다.

따라서 300은 가장 나중에 처리하자.

300들의 개수를 따로 저장해 놓는다.

    num300 = 0
    while start <= end and task[start] == 300: #300들 따로 저장
        num300 += 1
        start += 1

 

300 + 600 세트에서 어디 한쪽이 많은지에 상관없이, 위의 저장이 끝나면 301~600 범위의 서비스만 남는다.

엄밀히는 300이 많았다면 301~599, 600이 많았다면 301~600이지만 그냥 301~600범위라고 하자.

이 범위에서는 최대 2개까지 서버에 들어갈 수 있다.

따라서 앞에서 하나와 뒤에서 하나를 짝지어준다.

만약 뒤에 있는 서비스가 앞의 서비스와 매칭이 안되면(350, 599 같은 경우), 300짜리가 남아있을 경우 300과 매칭해준다.

300은 301~600 범위의 어떤 서비스와도 매칭이 가능하므로 300이 있기만 하다면 짝이 생성된다.

만약 300짜리가 없어서 end와 매칭되는 것이 없다면 이 친구는 혼자 서버를 사용해야하므로

서버 개수를 1개 늘리고 end를 하나 더 작은 서비스로 바꾼다. 

    while start < end:
        if task[start] + task[end] <= 900: #301~600에서 2개 세트 만들기
            servers += 1
            start += 1
            end -= 1
        elif num300 > 0: #세트 안만들어졌고, 300이 남은게 있었으면 end와 남았던 300매칭
            servers += 1
            num300 -= 1
            end -= 1
        else:
            servers += 1 #그것도 안되면 end하나 앞에꺼로
            end -= 1

계속 같은 방법으로 짝을 짓다보면 한개만 남는 경우가 있을 것이다.

이 친구한테는 당연히 하나의 서버가 온전히 할당된다.

만약에 300이 너무 많았으면 이때까지 남아있을 수 있는데, 혼자있는 서버에는 300하나는 무조건 더 들어갈 수 있다.

이제 남아있는 300들을 3개씩 묶어 서버에 할당해주면 된다.

num300+2를 3으로 나눈 몫을 사용한 이유는 3으로 나눠 떨어지면 그대로, 나눠떨어지지 않으면 몫에 1을 더해야하는데 이를 한번에 계산되도록 한 것이다.

    if start == end: #하나가 남았을 때 
        servers += 1
        if num300 > 0: #300이 남았으면
            num300 -= 1
    
    servers += (num300+2)//3
    print(servers)

 

위의 코드들을 위에서부터 순서대로 연결하면 문제를 해결할 수 있다.