백준 23291 어항정리 (C++)

문제를 풀때 삼성 문제답게 쪼개서 생각하는 것이 중요했습니다. 어항을 정리하는 두 개의 함수와 물고기를 옮기는 함수를 구현할 수 있습니다.

 

첫 번째 어항을 정리하는 과정은 문제에 설명하는 것을 다시 생각해보면 다음과 같이 달팽이 문제처럼 어항을 말아 올리는 과정을 구현하라는 것입니다.

1.
a b c d e f g h i j k

2.
a
b c d e f g h i j k

3.
b a
c d e f g h i j k

4.
c b
d a
e f g h i j k

5.
e d c
f a b
g h i j k

두 번째 어항을 정리하는 과정은 다음과 같이 생각해볼 수 있습니다.

1.
a b c d e f g h

2.
d c b a
e f g h

3.
f e
c d
b a
g h

즉, 배열을 4구역으로 나눈 뒤 3번째(역방향), 2번째(정방향), 1번째(역방향), 4번째(정방향) 순으로 저장하는 함수로 구현할 수 있습니다.

 

	#include <bits/stdc++.h>
	#define endl '\n'
	#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	using namespace std;
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll, ll> pll;
	const int INF=1e9+1;
	int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
	vector<vector<int>> flatten(vector<vector<int>>& v) {
	// 물고기 조절
	vector<vector<int>> r(v.size(),vector<int>(v[0].size()));
	for(int i=0;i<v.size();i++) {
	for(int j=0;j<v[0].size();j++) {
	if(!v[i][j]) continue;
	for(int k=0;k<4;k++) {
	int nx=i+dx[k],ny=j+dy[k];
	if(nx>=0 && nx<v.size() && ny>=0 && ny<v[0].size() && v[nx][ny] && v[nx][ny]<v[i][j]) {
	int fish=(v[i][j]-v[nx][ny])/5;
	r[nx][ny]+=fish, r[i][j]-=fish;
	}
	}
	}
	}
	return r;
	}
	pii f(int blen) {
	// 어항 개수에 따라 첫 번째 정리 과정에 필요한 배열의 크기를 리턴하는 함수
	for(int h=1;h<101;h++) {
	if(h*h<=blen && blen<(h+1)*h) return {h,h};
	if(h*(h-1)<=blen && blen<h*h) return {h,h-1};
	}
	return {0,0};
	}
	vector<int> f2(vector<vector<int>>& v) {
	// 어항 내 물고기를 조절한 후 다시 일차원 배열로 리턴하는 함수
	vector<int> r;
	auto d=flatten(v);
	for(int j=0;j<v[0].size();j++)
	for(int i=v.size()-1;i>=0;i--)
	if(v[i][j]+d[i][j]>0) r.push_back(v[i][j]+d[i][j]);
	return r;
	}
	vector<int> step1(vector<int>& board) {
	// 첫 번째 과정
	vector<vector<int>> v(20,vector<int>(20));
	auto [h,w] = f(board.size());
	int idx=h*w-1, x=h-1, y=w-1;
	while(idx>0) {
	// <
	while(y>0 && !v[x][y-1]) v[x][y--]=board[idx--];
	// ^
	while(x>0 && !v[x-1][y]) v[x--][y]=board[idx--];
	// >
	while(y<w-1 && !v[x][y+1]) v[x][y++]=board[idx--];
	// v
	while(x<h-1 && !v[x+1][y]) v[x++][y]=board[idx--];
	}
	v[x][y]=board[0];
	for(int i=0;i+h*w<board.size();i++) v[h-1][w+i]=board[h*w+i];
	return f2(v);
	}
	vector<int> step2(vector<int>& board) {
	// 두 번째 과정
	vector<vector<int>> v(4,vector<int>(board.size()/4));
	int a=board.size()/4, b=(board.size()/4)*2, c=(board.size()/4)*3;
	for(int i=c-1,j=0;i>=b;i--,j++) v[0][j]=board[i];
	for(int i=a,j=0;i<b;i++,j++) v[1][j]=board[i];
	for(int i=a-1,j=0;i>=0;i--,j++) v[2][j]=board[i];
	for(int i=c,j=0;i<board.size();i++,j++) v[3][j]=board[i];
	return f2(v);
	}
	int main() {
	fastio
	//freopen("input.txt","r",stdin);
	int n,k; cin>>n>>k;
	vector<int> board(n);
	for(auto& it : board) cin>>it;
	int iter=0;
	while(1) {
	// 종료조건과 가장 적은 물고기 수가 들어있는 어항에 물고기 하나
	int max_fish=*max_element(board.begin(),board.end());
	int min_fish=*min_element(board.begin(),board.end());
	if(max_fish-min_fish<=k) break;
	iter++;
	for(auto& it : board) if(min_fish==it) it++;
	// step1
	board=step1(board);
	// step2
	board=step2(board);
	}
	cout<<iter<<endl;
	return 0;
	}

view raw boj23291.cpp hosted with ❤ by GitHub