백준 33339 (C++) Group the Numbers

최초 업로드: 2025-09-20 11:02:57

최근 수정 시간: 2025-09-20 11:02:57

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] Group the Numbers

[문제 링크](https://www.acmicpc.net/problem/33339)

## 문제 설명

Consider the set of all integers from $1$ to $n$. Split these integers into $k$ equal-sized groups in such a way that the difference between the maximum and minimum sums of integers among all groups is minimized. Formally, if $s_i$ is the sum of integers in $i$-th group, the following value should be minimized:

$$\max\limits_{i=1}^k s_i - \min\limits_{i=1}^k s_i\text{.}$$

## 입력

The first line contains two integers $n$ and $k$ ($1 \leq n, k \leq 100\,000$; $n$ is divisible by $k$).

## 출력

For each group, print a line with all the integers belonging to that group. If there are multiple optimal answers, output any one of them.

## 풀이
- 가로의 길이가 짝수인 경우: 양 끝을 순서대로 넣음으로써 모든 그룹에 합을 같게 만들 수 있습니다.
- 가로의 길이가 1인 경우: 모든 그룹에 하나씩 집어넣어 차이는 n-1이 됩니다.
- 가로의 길이가 3이고 세로의 길이가 홀수인 경우: 1부터 k까지는 순서대로 그룹에 넣고, 2k부터 3k까지를 잘 조합해 합을 동일하게 만듭니다.

ex. 가로의 길이가 3, 세로의 길이가 5인 경우  
1 13 10  
2 14 8  
3 15 6  
4 11 9  
5 12 7  
이렇게 모든 그룹들의 합이 24가 되도록 구성할 수 있다.

- 가로의 길이가 3이고 세로의 길이가 짝수인 경우: 1부터 k까지는 순서대로 그룹에 넣고, 2k부터 3k까지를 잘 조합해 위의 절반의 그룹들이 아래 절반의 그룹들보다 1 크도록 조합한다.

ex. 가로의 길이가 3, 세로의 길이가 4인 경우  
1 11 8  
2 12 6  
3 9 7  
4 10 5  
이렇게 그룹들의 합이 순서대로 20, 20, 19, 19가 되도록 구성할 수 있다.

- 가로의 길이가 5 이상의 홀수인 경우: 길이 3까지는 이전의 과정과 동일하게 배치하고, 나머지는 짝수 개가 남았으므로, 짝수 길이일때처럼 합을 동일하게 그룹에 넣어주면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    int row = n/k;

vector<vector<int>> res(k+1);

if(row==1) {
 for(int i=1;i<=k;i++) res[i].push_back(i);
 } else if(row%2==0) {
 int l=1, r=n;
 for(int i=1;i<=k;i++) {
 for(int cnt=0;cnt<row/2;cnt++) res[i].push_back(l++);
 for(int cnt=0;cnt<row/2;cnt++) res[i].push_back(r--);
 }
 } else {
 for(int i=1;i<=k;i++) res[i].push_back(i);

if(k%2) {
 for(int i=1;i<=k/2+1;i++) res[i].push_back(3*k-k/2-1+i);
 for(int i=k/2+2;i<=k;i++) res[i].push_back(3*k-k+(i-k/2-1));

for(int i=1;i<=k/2+1;i++) res[i].push_back(k+1+2*(k/2+1-i));
 for(int i=k/2+2;i<=k;i++) res[i].push_back(k+2+2*(k-i));
 } else {
 for(int i=1;i<=k/2;i++) res[i].push_back(3*k-k/2+i);
 for(int i=k/2+1;i<=k;i++) res[i].push_back(3*k-k+(i-k/2));

for(int i=1;i<=k/2;i++) res[i].push_back(k+2*(k/2-i+1));
 for(int i=k/2+1;i<=k;i++) res[i].push_back(k+1+2*(k-i));
 }

for(int i=5;i<=row;i+=2) {
 for(int j=1;j<=k;j++) {
 res[j].push_back((i-2)*k+j);
 res[j].push_back(i*k+1-j);
 }
 }
 }

for(int i=1;i<=k;i++) {
 for(int e : res[i]) cout << e << ' ';
 cout << '\n';
 }
}
```