BOJ 2077 싼데 비슷한

문제 링크입니다.

문제 요약

$N$개의 칸에 광석이 묻혀 있습니다. 우리는 한 칸을 버리고 그다음 1~3칸에 묻혀 있는 광석을 얻을 수 있습니다. 첫 칸에는 항상 광석이 없습니다. 이때, 전체 광석 개수의 $3/4$ 이상을 얻으세요.

이때 메모리 제한이 상당히 작아, 각 칸에 몇 개의 광석이 묻혀있는 지를 모두 기록할 수 없습니다.

풀이

우리는 거꾸로 전체의 $1/4$ 이하의 광석이 묻힌 칸을 버리는 방법을 물색할 수 있습니다. 비둘기집 원리에 의해, 칸의 번호를 4로 나눈 나머지가 같은 칸끼리 묶었을 때 그 묶음들 중 적어도 하나는 묶음에 포함된 총 광석 개수가 전체의 $1/4$ 이하입니다.

해당 묶음에 포함된 칸들을 제거하는 건 시작점을 잘 잡고 나면 한 칸 버리고 다음 세 칸에 묻힌 광석들을 얻는 방법으로 쉽게 할 수 있습니다. 시작점을 잡는 부분이 약간 까다로운데, 문제 조건의 첫 칸이 비어있다는 특성을 이용하면 이 또한 처리할 수 있습니다. 따라서 조건에 맞게 광석을 얻는 방법은 항상 존재하며, 모든 칸의 광석 개수를 기록하는 대신 각 묶음의 총 광석 개수에 입력받은 광석 개수를 누적하는 방식으로 메모리를 아껴 정답을 구할 수 있습니다.

시간 복잡도는 $\mathcal{O}(N)$, 공간 복잡도는 $\mathcal{O}(1)$입니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll S[4];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T; cin >> T; while(T--){
		cout << "YES\n";
		int n; cin >> n; S[0] = S[1] = S[2] = S[3] = 0;
		for(int i = 1; i <= n; i++){
			int t; cin >> t; S[i%4] += t;
		}
		ll m = min({S[0], S[1], S[2], S[3]});
		if(S[2] == m){
			cout << "0"; n--;
		}
		else if(S[3] == m){
			cout << "01"; n -= 2;
		}
		else if(S[0] == m){
			cout << "022"; n -= 3;
		}
		while(n >= 4){
			n -= 4; cout << "0333";
		}
		if(n) cout << 0;
		if(n == 2) cout << 1;
		if(n == 3) cout << 22;
		cout << '\n';
	}
}