백준 2938, 3으로 나누어 떨어지지 않는 배열

개요

문제 링크
골드 5, 구성적
인접한 두 원소의 합이 3의 배수가 되지 않도록 배열 재배치하기

---

접근

1. 코드포스에서 자주 다루는 애드혹 사촌급의 구성적 알고리즘이다. 거기에 많은 조건분기까지 있다면? 어리버리까다가 제출 5번하고 점수는 점수대로, 시간은 시간대로, 멘탈은 멘탈대로 털리는 유형이다. 이 문제도 개인적으로 골5보다는 어렵지 싶다.

2. 문제로 돌아와서, 우선 mod3에 대해 조사할 것이니까 0,1,2가 있는데, 인접한 경우에서 합이 mod0 (3)이 되지 않는 경우는 (0,1),(0,2),(1,1),(2,2) 이다.

3. 그럼 우선 안되는 케이스를 생각해보자.

   1. 01020102와 같은 식으로 0과 0이 아닌 수를 번갈아 놓는다고 했을 때, 0이 절반 이상이면? 예를 들어 아래 케이스 같으면

       0 0 0 0 0 1 1 2
       -> 0 1 0 1 0 2 0 0

      어떻게 배치해도 0이 인접하게 남아버린다. 그럼 0이 (n+1)/2보다 많으면 안된다.
   2. 이때 n=1일 때를 생각해보자. 아래 케이스를 보면

       n=1
       [0]

      (n+1)/2=1이 되어버리고, 0의 개수는 1이므로 (n+1)/2 이하이다. 그래서 깔끔하게 0의 개수가 n일때도 안되는 조건에 추가해주자.
   3. 다음은 1과 2만 있을 때인데, 이때는 어떻게 배치해도 1과 2가 인접해버린다. 이때도 안된다.

4. 그럼 나머지는 크게 어렵지 않다. 0과 0사이에 1이나 2를 끼워넣고, 남으면 나머지를 쭉 이어서 출력해주면 된다. 그런데 아래 케이스를 보자.

    11
    0 0 0 1 1 1 1 1 2 2 2
   
    1 0 1 0 1 0 1 1 2 2 2

   0과 1,2를 번갈아서 배치하기만 하면 1과 2가 인접해버린다. 이걸 방지하기 위해 0이 하나남은 상황이면 아래와 같이 남은 1을 전부 출력해버리면 된다.

    0 1 0 1 1 1 1 0 2 2 2

   이때 pop함수를 만들어서 코드를 간소화하면 좋다.

---

Pseudo code

c0,c1,c2 = set(0,1,2) 
n0,n1,n2 = count(0,1,2) 
if (n0>(n+1)/2 || n0==n)
    return -1
if (n0==0 && n1 && n2)
    return -1
while (n0)
    if (n0 == 1)
        popAll(c1) // 남은1
    pop(c0) // 0
    if (n1) pop(c1) // 1
    else if (n2) pop(c2) // 2
popAll(c1)
popAll(c2)

---

Source code

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

#define sz size
#define pb push_back
using vec=vector<int>;
vec c0,c1,c2;

void pop(vec &a) {
    cout<<a.back()<<" ";
    a.pop_back();
}

bool get() {
    int n,x;
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>x;
        (x%3==1?c1:x%3==2?c2:c0).pb(x);
    }
    if (c0.sz()>(n+1)/2||c0.sz()==n)
        return 0;
    if (!c0.sz()&&c1.sz()&&c2.sz())
        return 0;
    while(c0.sz()) {
        if (c0.sz()==1)
            while(c1.sz())
                pop(c1);
        pop(c0);
        if (c1.sz()) pop(c1);
        else if (c2.sz()) pop(c2);
    }
    while(c1.sz()) pop(c1);
    while(c2.sz()) pop(c2);
    return 1;
}
int main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    if (!get()) cout<<-1;
}