BOJ 28302 - 팔찌
에디토리얼을 참고했다.
연산이 어떠한 특성을 가지는지를 파악하는 문제이다.
$x,y,z$로 색을 변경해서 생각하면
$$
\begin{aligned}
xy=z=yx \\
yz=x=zy \\
zx=y=xz
\end{aligned}
$$
가 되고 $ab=ba$ 이다. (교환법칙 성립)
따라서 모든 팔찌는 $x,y,z$ 의 개수로 표현된다.
$xyz$는 팔찌가 $xyz$가 아니라면 소거될 수 있다.
$x xyz=xyxz=zy=x$ 가 되기 때문이다.
또한, $x^2=y^2=z^2=xyz$ 이다.
길이 $2$ 이하의 팔찌는 $x^2,x,y,z$ 네 가지 경우만 있음을 파악한다.
네 가지 경우가 모두 다름은, 연산으로인한 불변이 무엇인지를 파악하면 된다.
$x=1,y=2,z=3$ 으로 대입하면 곱셈을 $\oplus$로 대신하면 그 값이 불변량이다.
$1 \oplus 1=0,~ 1, 2, 3$
따라서 일단 $s_1, s_2$가 동일한 타입을 가지는지 확인하자.
동일하다면 답을 구성하는 법은 일단 두 팔찌를 모두 $x^2, x,y,z$로 줄인다음에 두 번째 팔찌모양은 역으로 출력해주는 것으로 가능하다.
Comments