📝 문제 정보#
🧐 관찰 및 접근#
- 대칭이동을 어떻게 수학적으로 표현할 수 있을까??
- 쉬운거부터 해보자. 원래 점이 $(x, y)$에 있었다면
- $90\degree$ 직선에 대칭시키면 $(-x, y)$
- $45\degree$ 직선에 대칭시키면 $(y, x)$
- $60\degree$ 직선에 대칭시키면 $y = \sqrt{3}x$에 대칭인거니까… 아니 이거 너무 까다로운데?
- 행렬연산은 하기 싫은데..
- 각도를 기준으로 생각해보는것도 좋겠다. 극좌표계처럼, 원래 점이 $0\degree$에 있었다면
- $60\degree$에 대해 대칭시키면 $120\degree$에
- $120\degree$에 대해 대칭시키면 $240\degree$에
- 이런 느낌인 것 같다.
- 그렇다면 예제 1번은 $0\degree \rightarrow 120\degree \rightarrow 330 \degree \rightarrow 60 \degree \rightarrow 0$ 인거 같다!
- $45\degree = 225\degree$라고 생각하고, 가까운 곳을 찾아서 두배로 넘기고, 360으로 모듈러를 취하자.
- 쉬운거부터 해보자. 원래 점이 $(x, y)$에 있었다면
- 자, 이제 한번씩 써서 0도로 돌아오는걸 어떻게 만들지?
- $15\degree$로 만들 수 있는건 $30\degree$
- $x\degree$를 $a$에 대칭이동시키면 $(2a - x) \degree$가 되는 것 같다!
- 이걸 또 $b$에 대칭이동시키면 $(2b - (2a - x))\degree$ 인거같고.. 그러면 플마로 바뀌어가면서 더해지니까 결국 모듈러 360에 대해 두 그룹으로 나눈 합을 일정하게 맞출 수 있는지에 대한 문제로 바뀐다.
💻 풀이#
- 코드 (C++):
void solve(){
int N; cin >> N;
vector<int> A(N);
rep(i, 0, N) cin >> A[i];
if(N%2){
cout << "NO";
return;
}
int sum = 0;
for(auto x: A) sum += x;
sum %= 360;
DP[0][0][0] = true;
rep(i, 0, N) rrep(j, 0, N) rep(k, 0, 360) if(DP[i][j][k]){
int nxt = (k + A[i]*2) % 360;
DP[i+1][j+1][nxt] = true;
DP[i+1][j][k] = true;
}
if(DP[N][N/2][sum] || DP[N][N/2][(sum + 180) % 360]){
cout << "YES\n";
vector<bool> used(N);
int ci = N, cj = N/2, cs = sum;
if(!DP[N][N/2][sum]) cs = (sum + 180) % 360;
while(cj){
int prv = (cs - A[ci-1]*2) % 360;
if(prv < 0) prv += 360;
if(DP[ci-1][cj - 1][prv]){
used[ci-1] = true;
ci--;
cj--;
cs = prv;
}
else ci--;
}
vector<int> v1, v2;
rep(i, 0, N){
if(used[i]) v1.push_back(i+1);
else v2.push_back(i+1);
}
rep(i, 0, N/2){
cout << v1[i] << ' ' << v2[i] << ' ';
}
}
else cout << "NO";
}