[BOJ] 2938 3으로 나누어 떨어지지 않는 배열

문제

2938번: 3으로 나누어 떨어지지 않는 배열

자연수로 이루어진 배열이 주어졌을 때, 수의 순서를 적절히 바꿔서 인접한 두 수의 합이 3으로 나누어 떨어지지 않는 배열을 만드는 프로그램을 작성하시오.

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

풀이

1. 0이 연속으로 나올 수 밖에 없을 때

2. 1과 2가 붙을 수 밖에 없을 때

1. 1의 수(3으로 나누었을 때 나머지가 1)를 순서대로 ans에 push한다.

2. 만약, 1과 2가 모두 있다면 두 수 사이에 0(3으로 나누었을 때 나머지가 0)이 반드시 필요하므로 push해준다.

3. 2의 수(3으로 나누었을 때 나머지가 2) 순서대로 ans에 push한다.

4. 0의 수가 남아있다면 넣을 수 있는 공간에 알맞게 넣는다.

코드

#include <cstdio>
#include <vector>
 
using namespace std;
int n;
int arr[10000];
vector<int> v_1, v_2, v_0, ans;
 
void go() {
    int ix = v_0.size()-1;
    for(int i : v_1) ans.push_back(i);
    if (v_1.size() and v_2.size()) {
        ans.push_back(v_0[ix]);
        ix--;
    }
    for(int i : v_2) ans.push_back(i);
    for(int i = 0; i < ans.size(); i++) {
        if (ix >= 0 and arr[ans[i]] % 3) {
            if (i > 0 and arr[ans[i-1]] % 3) printf("%d ", arr[v_0[ix--]]);
            else if (i == 0) printf("%d ", arr[v_0[ix--]]);
        }
        printf("%d ", arr[ans[i]]);
    }
    if (ix == 0) printf("%d", arr[v_0[0]]);
}
 
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        if (arr[i] % 3 == 0) v_0.push_back(i);
        else if (arr[i] % 3 == 1) v_1.push_back(i);
        else v_2.push_back(i);
    }
    if (int(v_0.size() - v_1.size() - v_2.size()) > 1) {
        printf("-1");
        return 0;
    } else if (v_0.size() == 0 and v_1.size() > 0 and v_2.size() > 0) {
        printf("-1");
        return 0;
    }
    go();
}