문제 개요
네 면이 모두 거울로 덮여 있는 특별한 정사각형 방이 있다고 가정해 보겠습니다. 남서쪽 모서리를 제외한 나머지 세 개의 모서리에는 수광기(receptor)가 설치되어 있으며, 각각 0, 1, 2번으로 번호가 매겨져 있습니다. 방의 한 변의 길이는 p이고, 남서쪽 모서리에서 발사된 레이저 광선은 동쪽 벽에 처음 닿을 때 0번 수광기로부터 거리 q만큼 떨어진 지점을 맞힙니다. 우리가 구해야 할 것은 이 광선이 반사를 거듭한 끝에 최초로 도달하는 수광기의 번호입니다.
예시로 이해하기
p = 2, q = 1인 경우를 살펴보겠습니다.
이때 출력 결과는 2입니다. 광선이 여러 차례 반사된 뒤 처음으로 왼쪽 벽에 도달하는 지점이 바로 2번 수광기이기 때문입니다.
해결 전략: 홀짝성(패리티) 분석
이 문제는 광선의 실제 경로를 일일이 추적할 필요가 없습니다. 핵심은 p와 q의 홀짝성에 있습니다. 알고리즘은 다음과 같습니다.
- p와 q가 모두 짝수인 동안 두 값을 계속 2로 나눕니다.
- 나눈 후 p가 짝수라면 2를 반환합니다.
- q가 짝수라면 0을 반환합니다.
- 둘 다 홀수라면 1을 반환합니다.
왜 이 방법이 작동할까요?
거울방을 무한한 격자 형태로 펼쳐 놓으면, 광선은 반사 없이 곧게 나아가는 직선이 됩니다. 이 직선이 어떤 방의 모서리에 도달하는 시점은 가로로 p/gcd(p, q)칸, 세로로 q/gcd(p, q)칸을 이동했을 때입니다. 알고리즘에서 공통 인수 중 2만 제거해도 홀짝성은 그대로 유지되므로 결과는 동일합니다.
- 가로 이동 횟수가 홀수면 동쪽 벽, 짝수면 서쪽 벽에 도달합니다.
- 세로 이동 횟수가 홀수면 위쪽 모서리, 짝수면 아래쪽 모서리에 도달합니다.
이를 조합하면 다음과 같은 규칙이 성립합니다.
- p가 홀수이고 q가 홀수 → 북동쪽 모서리 → 1번
- p가 짝수이고 q가 홀수 → 북서쪽 모서리 → 2번
- p가 홀수이고 q가 짝수 → 남동쪽 모서리 → 0번
C++ 구현
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int mirrorReflection(int p, int q) {
while(p % 2 == 0 && q % 2 == 0){
p >>= 1;
q >>= 1;
}
if(p % 2 == 0) return 2;
if(q % 2 == 0) return 0;
return 1;
}
};
main(){
Solution ob;
cout << (ob.mirrorReflection(2, 1));
}
실행 결과
입력:
2
1
출력:
2
복잡도 분석 및 마무리
이 알고리즘은 반복문에서 p와 q를 계속 절반씩 줄이므로 시간 복잡도는 O(log(min(p, q)))이며, 추가 메모리를 사용하지 않아 공간 복잡도는 O(1)입니다. 복잡한 시뮬레이션 없이도 수학적 성질만 활용하면 거울방 속 레이저의 최종 도착 지점을 즉시 계산할 수 있다는 점이 이 문제의 핵심입니다.