10. 1초에 한칸씩 격자를 움직이는 개미의 n초후 좌표 찾기

## 문제 ##

아래의 그림처럼 1초에 한칸씩 이동하는 개미가 있다.

이 개미는 아래의 표에 나와있는 숫자 규칙대로 이동을 한다.

우리는 수 초 뒤에 개미가 과연 어떤곳에 위치하고 있는지를 알고 싶다!! (x < 200, y < 200)

 

사용자가 임의의 숫자(초)를 입력하면 개미의 위치를 좌표로 출력한다.

 

eg) input : 1, output : (1,1)

    input : 3 , output : (2,2)

    input : 12, output : (4,3)

 

## 풀이 ##

문제에 의하면 아래와 같은 표가 성립

idx:    Range    Direction

------------------------------
1:      1        R(Right)
2:      2~4      U(Upper)
3:      5~9      R
4:      10~16    U
5:      17~25    R

...

 

따라서, 아래와 같은 스텝으로 좌표 구할수 있음

*알고리즘

input:a

1)find idx from the input a
  idx = (int)sqrt(a-1) + 1

2)find direction
  dir = (idx % 2) == 0 ? U : R

3)find middle value of the range
  m = (idx ^ 2) - (idx - 1)

4)find (x,y)
  if dir == u
     if a<= m --> x=idx; y=idx-(m-a)
     if a>m -->  x=idx-(a-m); y=idx
  if dir == r
     if a<= m -->  x = idx-(m-a); y=idx
     if a>m -->  x=idx; y=idx-(a-m)

 

* 검증

 a = 8 --> (3,2)

 idx = (int)sqrt(a-1) + 1 = 3

 dir = (idx % 2) == 0 ? U : R = R

 m = (idx ^ 2) - (idx - 1) = 9 - 2 = 7

 

 a > m --? x=idx; y=idx-(a-m)

     x=3  y=3-(8-7)=2  ==>(3,2)

 

 

## 소스코드 ##