[BOJ 12886] 돌 그룹
문제 출처 : https://www.acmicpc.net/problem/12886
풀이
이 문제를 BFS 를 이용해 완전 탐색의 기법으로 풀어낼 수 있다.
이 때, $500^3$ 을 배열로 잡을 수가 없어서 헤맬 수 있으나,
\[A+B+C = sum \\ C = sum-A-B\]이라는 간단한 수학을 이용하면 $500^2$ 의 공간을 가지고 탐색을 진행할 수 있다.
물론 500 만큼만 잡으면 탐색을 하는데 조금 문제가 있을 수 있는데, 500보다 큰 범위로 배열을 설정해주어야 한다.
X+X 와 Y-X 로 각각 변화하는 숫자에 있어서 최대 최소는 각각 0~1000 임을 생각할 수 있다.
따라서 공간 복잡도는 $1000^2$ 이 된다.
이것을 구현하는 방법은 다양할 수 있는데, 아래는 아주 대충 짠 코드이다.
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int MAX = 1010;
bool check[MAX][MAX];
queue<pii> q;
int main(){
int A, B, C;
cin >> A >> B >> C;
int sum=A+B+C;
if(sum%3){
cout << 0;
return 0;
}
if(A==B && B==C){
cout << 1;
return 0;
}
int M = sum/3;
if(A>C){
swap(A,C);
}
if(A>B){
swap(A,B);
}
// A < B < C;
check[A][B]=1;
pii k;
k = make_pair(A,B);
q.push(k);
check[A][C]=1;
k = make_pair(A,C);
q.push(k);
check[B][C]=1;
k = make_pair(B,C);
q.push(k);
while(!q.empty()){
k=q.front();
q.pop();
A=k.first, B=k.second;
C = sum-A-B;
int na = A*2, nb=B-A;
if(na>1000 || nb>1000 || C>1000) continue;
if(na<=0 || nb<=0 || C<=0) continue;
//cout << A << " " << B << " " << C << endl;
pii nk;
if(na>nb){
if(!check[nb][na]){
check[nb][na] = 1;
nk = make_pair(nb,na);
}
}
else {
if(!check[na][nb]){
check[na][nb] = 1;
nk = make_pair(na,nb);
}
}
q.push(nk);
if(na<C){
if(!check[na][C]){
check[na][C] = 1;
nk=make_pair(na,C);
}
}
else{
if(!check[C][na]){
check[C][na]=1;
nk=make_pair(C,na);
}
}
q.push(nk);
if(nb<C){
if(!check[nb][C]){
check[nb][C] = 1;
nk=make_pair(nb,C);
}
}
else{
if(!check[C][nb]){
check[C][nb]=1;
nk=make_pair(C,nb);
}
}
q.push(nk);
}
cout << check[M][M];
return 0;
}
수학적 접근
그러나 이 문제는 이러한 완전탐색 기법을 적용하는 문제는 아니다.
세 가지 수가 모두 같은 수가 되려면 어떤 상태인 것인가?
바로 평균 이다.
즉, 세 수의 합이 3의 배수가 아니면 답은 자명하게도 0 이 나와야 한다.
그렇다면 세 수의 합이 3의 배수이면 답은 1 인가?
그렇지는 않다.
해당 문제를 보면 작은 수 X 는 X+X 가 되어 2X 가 되게 되고, 큰 수 Y 는 Y-X 가 된다.
여기서 착안해서 다음과 같은 접근을 할 수 있다.
- 입력값의 합은 3의 배수여야한다.
- 입력값들의 최대공약수로 합을 나눴을 때도 3의 배수여야 한다.(1의 계산은 여기서 합쳐진다.)
- 2에서 계산된 값은 $2^k \times 3$ 꼴이어야 한다.
어떻게 이런 접근 방법이 나왔을까?
핵심은 X+X=2X, Y-X 가 되면서 다음으로 진행된다는 것이다.
즉, 한 step 마다 수식(또는 인수라고도 생각할 수 있다)에 소인수 2가 추가되는 것이고, 결국 최종적으로 세 수가 같아지는 평균 M에는 몇 개의 소인수 2가 있을 것이다. 즉 $2^k$ 형태가 되게 된다.
조금 엄밀하게 말하자면, $M = 2^k * G$ 의 꼴이 될 것인데, 여기서의 $G$ 가 바로 최대공약수(gcd) 이다.
#include <iostream>
using namespace std;
int gcd(int x, int y){
if(y==0) return x;
x%=y;
return gcd(y,x);
}
int cal_bit(int k){
int ret=0;
for(int i=0; i<32; i++){
ret+=k%2;
k=k>>1;
}
return ret;
}
int main(){
int A, B, C;
cin >> A >> B >> C;
int q=(A+B+C)/(gcd(A, gcd(B,C)));
cout << (q%3==0 && cal_bit(q/3)==1);
return 0;
}
개선할 점
- naive BFS 코드에서 모듈화하면 코드가 간결해진다. 리팩토링을 해보자.
- 수학적 접근 방법에서 엄밀한 증명이 필요하다.
- gcd 와 cal_bit 를 내장 함수(**gcd, **builtin_popcount)를 사용할 경우 코드가 간결해진다.
Leave a comment