[BOJ]17245 서버실

https://www.acmicpc.net/problem/17245

---

문제

서버실은 여러 대의 서버 컴퓨터들을 안정적으로 운영할 수 있는 환경을 유지하기 위해 설치된 공간을 말한다.

이 회사의 서버실은 N×N 칸으로 구분되어 있고, 각 칸마다 서버 랙이 있어 컴퓨터를 여러 대 쌓을 수 있다. 서버가 과열되지 않도록 서버실에는 언제나 냉방기가 작동하고 있다. 그런데 회사가 경제적으로 어려움에 처한 나머지, 서버실의 운영 비용을 줄이기 위해 서버실 내의 컴퓨터 중 절반만 정상적으로 관리하기로 하였다.

냉방기에서 나온 차가운 공기는 서버실의 아래쪽부터 서서히 차오른다. 1분마다 컴퓨터 한 대의 높이만큼 방을 채운다. 이 회사의 서버 컴퓨터는 환경에 매우 민감하여 차가운 공기를 받아야만 동작하고 그렇지 못하면 장애를 일으킨다.

서버실의 컴퓨터 중 절반 이상이 켜지려면 몇 분이 필요할까?

입력

정수 N이 주어진다. (1 ≤ N ≤ 1000)

N×N개의 각 칸에 컴퓨터가 몇 대 쌓여있는지가 입력된다. 한 칸에는 최대 10,000,000대까지 쌓여있을 수 있다.

출력

몇 분이 지나야 전체 컴퓨터의 절반 이상이 장애를 일으키지 않고 동작할 수 있는지 출력한다.

예제 입력 1 

5
1 4 0 2 1
0 0 5 6 3
8 4 7 2 0
7 1 0 5 3
4 5 7 9 1

예제 출력 1

3

---

구상

i초에 새로 켜지는 컴퓨터는 (전체 컴퓨터 층의 수) - (i보다 작게 쌓인 컴퓨터 층의 수)이다.

예를 들어 2 x 2 컴퓨터 층이 있다고 하자. (즉 컴퓨터 층의 갯수는 총 4개이다)

0 1

2 3

이렇게 컴퓨터가 쌓여있을 때,

0초에는 아무것도 켜지지 않는다.

1초에는 0개가 쌓인 컴퓨터 층을 제외한 모든 컴퓨터 층에서 한개씩 새로 컴퓨터가 켜진다.( 4 - comp[0])

2초에는 0개, 1개가 쌓인 컴퓨터 층을 제외한 모든 컴퓨터 층에서 한개씩 ( 4  - (comp[0] + comp[1]) )

3초에는 0개, 1개, 2개가 쌓인 컴퓨터 층을 제외한 모든 컴퓨터 층에서 한개씩 새로 컴퓨터가 켜진다.

컴퓨터 층이 정렬되어 있다고 가정하면, 다음과 같이 그림으로 나타낼 수 있다

따라서 dp를 통해 i초 일 때, i-1만큼 쌓인 층을 저장하여 계산하면 되겠다고 생각했다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main(){
    int n = 0;
    scanf("%d",&n);
    int m = n*n;
    int ans = 0;
    long long tot = 0;
    int comp[10000001] = {0,}; //comp[x] = x층이 쌓인 컴퓨터의 수
    int dp[10000001] = {0,}; // dp[x] = x보다 작은 모든 comp의 수. 즉 comp[0] + comp[1] + ... + comp[x-1]
    for(int i = 0; i < m; i++){
        int tmp;
        scanf("%d",&tmp);
        tot += tmp;
        comp[tmp]++;
    }
    long long computerNotPowered = tot; //0초에는 모든 컴퓨터가 꺼져있다

    dp[1] = comp[0];
    for(int i = 1; i < 10000001; i++){
        //i초에 새로 켜지는 컴퓨터의 수 : n x n 컴퓨터 탑 중, i개보다 낮게 쌓이지 않은 모든 컴퓨터( m - dp[i] )
        //예를 들어 3초에는 comp[0], comp[1], comp[2]를 제외한 모든 컴퓨터가 새로  켜진다.
        computerNotPowered -= (m-dp[i]);
        if(!(computerNotPowered >= tot/2)){ //켜진 컴퓨터의 수가 절반보다 크거나 같은 경우(== 켜지지 '않은' 컴퓨터가 절반보다 크거나 같지 '않은' 경우)
            ans = i;
            break;
        }
        dp[i+1] = comp[i] + dp[i];
    }
    printf("%d",ans);
    return 0;
}

하지만 틀렸다. 왜지?

도저히 모르겠어서 코드를 약간만 수정하기로 했다.

0초부터 꺼진 컴퓨터를 세는 것이 아닌 1000000초부터 켜진 컴퓨터를 하나씩 끄기로 한 것.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main(){
    int n = 0;
    scanf("%d",&n);
    int m = n*n;
    int ans = 0;
    long long tot = 0;
    int comp[10000001] = {0,}; //comp[x] = x층이 쌓인 컴퓨터의 수
    int dp[10000001] = {0,}; // dp[x] = x보다 큰 모든 comp의 수. 즉 comp[x] + comp[x+1] + ... + comp[10000000]
    for(int i = 0; i < m; i++){
        int tmp;
        scanf("%d",&tmp);
        tot += tmp;
        comp[tmp]++;
    }
    long long standard = ((tot%2 == 0) ? tot/2 : tot/2+1);
    long long computerPowered = tot; //10000000초에는 모든 컴퓨터가 켜져있다.

    dp[10000000] = comp[10000000];
    for(int i = 10000000; i > 0; i--){
        //i초에 i보다 높게 쌓인 컴퓨터는 꺼짐( dp[i] )
        computerPowered -= dp[i];
         if(!(computerPowered >= standard)){ //처음으로 절반보다 작아진 경우, 이번에 컴퓨터가 꺼지면 안된다는 뜻이므로 현재 초를 리턴
            ans = i;
            break;
        }
        dp[i-1] = comp[i-1] + dp[i];
    }
    printf("%d",ans);
    return 0;
}

이 코드로는 모든 테스트케이스를 통과했다.

입력 예제로 1 3이나 1 1 등을 넣어보면서 total / 2가 홀수,짝수였을 경우마다 값이 다르게 나오는 것을 확인했다. 아마 첫 코드도 이를 고려하지 않아서 생긴 문제인듯.