1125번 : 바닥 장식

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

1125번: 바닥 장식

어떠한 구역에서 바닥 장식 크기마다 개수를 다 구해주고, 그 개수들을 이용해서 1x5 나무 판을 최소한으로 사야하는 문제다.

 

아이디어 : 

첫 번째. 1x1, 1x2, 1x3, 1x4, 1x5 타일이 각각 몇개씩 필요한지 찾는다.
두 번째. 구매해야하는 1x5타일 개수의 최소값을 찾는다.

우선 주어진 구역보다 작은, 5x5 격자에 딱 맞는 직사각형을 하나 더 찾는다.

문제의 예시에선 저 보라색 직사각형이 나올 것이다.

일반적으로 위와 같은 모양이 나올 것이다. xx1, yy1, xx2, yy2는 무조건 5의 배수가 된다. 이제 구역을 나누어서 타일 개수를 구할 것이다.

타일 개수를 다 구했으면 이제 1x5 타일을 몇개 구매해야 하는지 구해야 한다.

우선 1x5타일을 먼저 만드는게 항상 좋으므로 
(5), (4,1), (3,2), (3,1,1), (2,2,1), (2,1,1,1), (1,1,1,1,1) 으로 묶어본다.

다음은 1x4타일이다.
(4), (3,1), (2,2), (2,1,1), (1,1,1,1)

다음은 1x3타일
(3), (2,1), (1,1,1)

다음은 1x2타일
(2), (1,1)

마지막으로 1x1타일
(1)

으로 묶어본다. 묶을 때 마다 구매해야 할 타일 개수 +1개씩 해준다.

구현 : 

구역을 나눌 때 xx1이 xx2보다, yy1이 yy2보다 클 수도 있다. 이런 경우는 예외처리를 해주어야 한다.

구현을 좀 더 쉽게 하기 위해 임의의 구역 (x1,y1) ~ (x2,y2)에서 나오는 타일 개수를 세주는 f(x1,y1,x2,y2)를 정의해주었다. (단, 이 구역은 5x5 단위 타일을 벗어나지 않는다.)
(x1,y1)을 기준으로 x1/5 + y1/5가 짝수인지 홀수인지에 따라 가로로 5개 있는 모양인지, 세로로 5개 있는 모양인지 판별 해주었다.

코드 : 

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
vector<ll> f(ll x1, ll y1, ll x2, ll y2){
	vector<ll> ret(6,0);
	if(x1>x2 || y1>y2) return ret;
	if(x2-x1>5 && y2-y1>5) return ret;
	if((x1/5+y1/5)%2){
		ret[y2-y1]+=x2-x1;
	}
	else{
		ret[x2-x1]+=y2-y1;
	}
	return ret;
}
int main(){
	ll x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;

	vector<ll> r(6,0);
	vector<ll> t(6,0);
	ll xx1,yy1,xx2,yy2; // 5,5 격자에 맞춘 값
	xx1=x1+(5-x1%5)%5;
	yy1=y1+(5-y1%5)%5;
	xx2=(x2/5)*5;
	yy2=(y2/5)*5;
	// cout << "xx1 : " << xx1 << ", yy1 : " << yy1 << ", xx2 : " << xx2 << ", yy2 : " << yy2  << '\n';
	if(xx1>xx2 && yy1>yy2){ // 같은 영역 안에 있음
		t=f(x1,y1,x2,y2);
		for(int j=1; j<=5; ++j){
			r[j]+=t[j];
		}
	}
	else if(xx1>xx2){
		if(y1%5){
			t=f(x1,y1,x2,(y1/5+1)*5);
			for(int j=1; j<=5; ++j){
				r[j]+=t[j];
			}
			y1=(y1/5+1)*5;
		}
		if(y2%5){
			t=f(x1,(y2/5)*5,x2,y2);
			for(int j=1; j<=5; ++j){
				r[j]+=t[j];
			}
			y2=(y2/5)*5;
		}
		for(int i=y1; i<y2; i+=5){
			t=f(x1,i,x2,i+5);
			for(int j=1; j<=5; ++j){
				r[j]+=t[j];
			}
		}
	}
	else if(yy1>yy2){
		if(x1%5){
			t=f(x1,y1,(x1/5+1)*5,y2);
			for(int j=1; j<=5; ++j){
				r[j]+=t[j];
			}
			x1=(x1/5+1)*5;
		}
		if(x2%5){
			t=f((x2/5)*5,y1,x2,y2);
			for(int j=1; j<=5; ++j){
				r[j]+=t[j];
			}
			x2=(x2/5)*5;
		}
		for(int i=x1; i<x2; i+=5){
			t=f(i,y1,i+5,y2);
			for(int j=1; j<=5; ++j){
				r[j]+=t[j];
			}
		}
	}
	else{
		r[5]+=(((xx2-xx1)/5)*((yy2-yy1)/5))*5;
		//구해야 할 구역은 총 8 구역
		// 1. (x1,y1) ~ (xx1,yy1)
		if(x1<xx1 && y1<yy1){
		    t=f(x1,y1,xx1,yy1);
		    for(int j=1; j<=5; ++j){
			    r[j]+=t[j];
		    }
		}
	
		// 2. (xx1,y1) ~ (xx2,yy1)
		if(xx1<xx2 && y1<yy1){
		    r[5]+=((xx2-xx1)/10)*(yy1-y1);
		    r[yy1-y1]+=((xx2-xx1)/10)*5;
		    if((xx2-xx1)%10==5){
			    t=f(xx1,y1,xx1+5,yy1);
			    for(int j=1; j<=5; ++j){
				    r[j]+=t[j];
			    }
		    }
		}
		// 3. (xx2,y1) ~ (x2,yy1)
		if(xx2<x2 && y1<yy1){
		    t=f(xx2,y1,x2,yy1);
		    for(int j=1; j<=5; ++j){
			    r[j]+=t[j];
		    }
		}
		// 4. (x1,yy1) ~ (xx1,yy2)
		if(x1<xx1 && yy1<yy2){
		    r[5]+=((yy2-yy1)/10)*(xx1-x1);
		    r[xx1-x1]+=((yy2-yy1)/10)*5;
		    if((yy2-yy1)%10==5){
			    t=f(x1,yy1,xx1,yy1+5);
			    for(int j=1; j<=5; ++j){
				    r[j]+=t[j];
			    }
		    }
		}
		
		// 5. (xx2,yy1) ~ (x2,yy2)
		if(xx2<x2 && yy1<yy2){
		    r[5]+=((yy2-yy1)/10)*(x2-xx2);
		    r[x2-xx2]+=((yy2-yy1)/10)*5;
		    if((yy2-yy1)%10==5){
			    t=f(xx2,yy1,x2,yy1+5);
			    for(int j=1; j<=5; ++j){
				    r[j]+=t[j];
			    }
		    }
		}
		// 6. (x1,yy2) ~ (xx1,y2)
		if(x1<xx1 && yy2<y2){
		    t=f(x1,yy2,xx1,y2);
		    for(int j=1; j<=5; ++j){
			    r[j]+=t[j];
		    }
		}
		// 7. (xx1,yy2) ~ (xx2,y2)
		if(xx1<xx2 && yy2<y2){
	    	r[5]+=((xx2-xx1)/10)*(y2-yy2);
		    r[y2-yy2]+=((xx2-xx1)/10)*5;
		    if((xx2-xx1)%10==5){
			    t=f(xx1,yy2,xx1+5,y2);
			    for(int j=1; j<=5; ++j){
				    r[j]+=t[j];
			    }
		    } 
		}
		// 8. (xx2,yy2) ~ (x2,y2)
		if(xx2<x2 && yy2<y2){
		    t=f(xx2,yy2,x2,y2);
		    for(int j=1; j<=5; ++j){
			    r[j]+=t[j];
		    }
		}
	}
	ll res=0;
	ll k;
	res+=r[5];
	r[5]=0;
	k=min(r[4],r[1]);
	res+=k;
	r[4]-=k;
	r[1]-=k;
	k=min(r[3],r[2]);
	res+=k;
	r[3]-=k;
	r[2]-=k;
	k=min(r[3],r[1]/2);
	res+=k;
	r[3]-=k;
	r[1]-=k*2;
	k=min(r[2]/2,r[1]);
	res+=k;
	r[2]-=k*2;
	r[1]-=k;
	k=min(r[2],r[1]/3);
	res+=k;
	r[2]-=k;
	r[1]-=k*3;
	res+=r[1]/5;
	r[1]%=5;
	res+=r[4];
	r[4]=0;
	k=min(r[3],r[1]);
	res+=k;
	r[3]-=k;
	r[1]-=k;
	res+=r[2]/2;
	r[2]%=2;
	k=min(r[2],r[1]/2);
	res+=k;
	r[2]-=k;
	r[1]-=k*2;
	res+=r[1]/4;
	r[1]%=4;
	res+=r[3];
	r[3]=0;
	k=min(r[2],r[1]);
	res+=k;
	r[2]-=k;
	r[1]-=k;
	res+=r[1]/3;
	r[1]%=3;
	res+=r[2];
	r[2]=0;
	res+=r[1]/2;
	r[1]%=2;
	res+=r[1];
	cout << res << '\n';
	
}

 

예외 처리가 아주 많이 힘들었다..