BOJ 31873 : 별 수호자 룰루

• 문제 링크 : boj.kr/31873
• 난이도 : G2
• 태그 : 해 구성하기, 애드혹

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;
    if(k == 1 || (k == n && k % 2 == 1)) {
        cout << "NO";
        return 0;
    }

    cout << "YES\n";
    int t = n/k;
    for(int i = 1; i <= t; i++) {
        if(t % k == 1) {
            if(k == 2) {
                cout << i << " ";
            }
            else {
                cout << (i+1) % t + 1 << " ";
            }
        }
        else {
            cout << (i % t) + 1 << " ";
        }
        for(int j = 1; j < k; j++) {
            cout << i + j * t << " ";
        }
        cout << "\n";
    }

    return 0;
}

---

풀이

불가능한 경우부터 제외하자. k가 1인 경우 당연히 불가능하고, k==n인 동시에 k가 홀수라면 불가능하다.

 

가능한 경우는 잘 나누어주어야 한다. n/k를 t라고 하자.

우선 대부분의 경우에 {a, a+t, a+2t, ... a+(k-1)t}의 합은 k의 배수이다.

이때 대부분의 경우는 첫 항 a를 a%t+1로 바꿔주는 것으로 해결이 가능하다.

 

단 t%k가 1인 경우에는 어떤 별의 합이 k의 배수가 되므로 예외처리를 해주어야 한다.

k가 2인 경우에는 합이 k의 배수를 만족하지 못하므로 그대로 사용한다.

k가 2가 아닌 경우에는 a를 (a+1)%t+1로 바꿔주어 해결할 수 있다.