BOJ 1491 - 나선

문제

BOJ 1491 - 나선

N×M 격자에서 나선형으로 이동할 때, 이동 거리가 정확히 K번째가 되는 지점의 좌표를 구하는 문제다. 나선은 오른쪽, 아래, 왼쪽, 위 방향으로 반복하며 이동 거리는 1씩 증가한다.

실제 문제는 입력 N과 M이 주어지면, M번째 이동이 끝나는 지점의 좌표(행, 열)를 출력한다. N이 M 이상인 경우와 미만인 경우로 나누어 공식을 적용한다.

입력

첫째 줄에 정수 N, M이 주어진다.

출력

M번째 이동이 끝나는 지점의 행, 열을 공백으로 구분하여 출력한다.

예제

풀이

나선 이동의 패턴을 수식으로 정리하여 직접 계산하는 수학적 접근을 사용한다.

1. N이 M 이상인 경우:
   • M이 짝수이면 행 = M/2 - 1, 열 = M/2
   • M이 홀수이면 행 = N - M/2 - 1, 열 = M/2
2. N이 M 미만인 경우:
   • N이 짝수이면 열 = N/2
   • N이 홀수이면 열 = M - N/2 - 1
   • 행 = (N-1)/2

핵심 아이디어: 나선 이동의 대칭성을 이용해 N과 M의 대소 관계에 따라 행/열 방향을 분리하면 O(1) 공식으로 계산할 수 있다.

코드

#include <iostream>
 
using namespace std;
 
int main()
{
  int N, M, x;
  cin >> N >> M;
 
  if (N >= M)
  {
    if (M % 2 == 0)
      x = M / 2 - 1;
    else
      x = N - M / 2 - 1;
    cout << x << " " << M / 2 << endl;
  }
  else
  {
    if (N % 2 == 0)
      x = N / 2;
    else
      x = M - N / 2 - 1;
    cout << (N - 1) / 2 << " " << x << endl;
  }
  return 0;
}

복잡도

• 시간: O(1) — 수식으로 직접 계산
• 공간: O(1) — 변수 몇 개만 사용