문제
N×N 타일 위에 K개의 말이 놓여 있다. 각 말의 위치 (x, y)에 대해 타일의 대칭성을 이용하여 대표 좌표로 변환한 후, 특정 규칙에 따라 1, 2, 3 중 하나의 숫자를 출력하는 문제다.
입력
- 첫 줄에 N과 K가 주어진다.
- 이후 K줄에 걸쳐 말의 위치 x, y가 주어진다.
출력
- 각 말에 대해 1, 2, 3 중 하나를 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 3 1 1 2 3 3 4 | 1 2 3 |
풀이
타일의 대칭성을 이용해 좌표를 정규화한 뒤 y좌표의 3으로 나눈 나머지로 답을 결정한다.
- 각 좌표가 중앙(N+1)/2을 초과하면 반대쪽 대칭 좌표로 변환한다:
x = N + 1 - x. - x와 y 중 큰 값을 x로, 작은 값을 y로 교환하여 정규화한다.
- 정규화된 y를 3으로 나눈 나머지에 따라 출력: 나머지 1이면
1, 2이면2, 0이면3.
핵심 아이디어: 타일의 4방향 대칭성을 활용해 모든 좌표를 1사분면의 대표 좌표로 매핑하면, y의 3주기 패턴으로 답을 구할 수 있다.
코드
#include <cstdio>
int main(void)
{
int N, K, x, y, temp;
scanf("%d %d", &N, &K);
for (int i = 0; i < K; i++)
{
scanf("%d %d", &x, &y);
if (x > (N + 1) / 2)
x = N + 1 - x;
if (y > (N + 1) / 2)
y = N + 1 - y;
if (x < y)
{
temp = x;
x = y;
y = temp;
}
if (y % 3 == 1)
printf("1\n");
if (y % 3 == 2)
printf("2\n");
if (y % 3 == 0)
printf("3\n");
}
}복잡도
- 시간: O(K) — K개의 말을 각각 O(1)에 처리
- 공간: O(1)