[백준/BOJ] 32990 시설물 사용 신청

문제 : 32990번: 시설물 사용 신청

신청을 하는 시간기준으로 나누어 생각하면

시간대의 길이가 x일 때 최대 강의실 x개 안에 나눌 수 있음을 알 수 있다.

이때, x가 N/2보다 크다면 각 시간대 별로 하나의 강의실을 차지하므로

N-x개의 강의실에만 배치해도 된다.

 

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (ll i=1;i<N;i++){
        if (N>=i*2)
            ans+=i; // 같은 강의실을 여러번 사용하는 경우
        else
            ans+=N-i; // 한번만 사용하는 경우
    }
    cout << ans << "\n";
    if (ans>1000000)
        return 0;
    for (ll i=1;i<N;i++){
        for (ll j=1;j<=i;j++){
            ll cnt=(N-j)/i;
            if (cnt)
                cout << cnt << " "; // 현재 강의실을 총 몇번 사용하는지 출력
            for (ll k=j;k<=N-i;k+=i)
                cout << k << " " << k+i << " "; // 사용하는 각 시간대 출력
            if (cnt)
                cout << "\n";
        }
    }
    return 0;
}