1차원 큰 이동

문제

---

1 번부터 n 번까지 총 n 개의 공간이 있는 1차원 배열의 x 번 위치에 사람이 있다. 이 사람은 초기 방향 d 로 1 초에 한 칸 씩 이동하는데, 배열의 끝에 도착하면 다음 이동 시 뒤로 돌아서 반대 방향으로 이동한다. t 초 뒤 이 사람의 위치와 방향을 출력하여라.

d 가 0 이면 좌표가 감소하는 방향, d 가 1이면 좌표가 증가하는 방향으로 이동한다.

입력

---

첫 줄에 정수 n, x, d, t 가 주어진다.

(3 ≤ n ≤ 1,000,000,000, 1 ≤ x ≤ n, 0 ≤ d ≤ 1, 0 ≤ t ≤ 1,000,000,000)

출력

---

t 초 후 사람의 위치와 방향을 출력한다.

입력의 예 1

6 4 0 5

출력의 예 1

3 1

입력의 예 2

5131 555 0 35491

출력의 예 2

4158 1

입력의 예 3

21354 3124 0 861231

출력의 예 3

3989 1

입력의 예 4

463571372 78942314 1 1000000000

출력의 예 4

151799572 1

 

 

반복문을 사용하여 풀이하면 시간 초과가 걸린다

-> n과 t가 1억 제한이 있으므로 둘다 1억일경우 초과걸린다.

 

따라서 규칙에 의해 t 와 x를 초기화해주어야 함

 

#include <stdio.h>
int n, x, d, t;
int dr[2] = {-1, 1};

int main() {
  scanf("%d %d %d %d", &n, &x, &d, &t);
  
  t %= (2*n -2); //벗어나는 경우를 대비하여 정규화
  
  //움직이는 값을 1~n 안에 들어오도록 반복적으로 scaling
  while(x + t * dr[d] < 1 || x + t * dr[d] > n){
    if (x + t* dr[d] < 1){
      t -= x-1; //이렇게 해주면 거꾸로 돌아가는만큼 시간 차감
      x = 1;//초기화
      d = 1;//방향전환
    }
    else if (x + t* dr[d] > n){
      t -= n-x;
      x = n;
      d = 0;
    }
  }
  
  //이제 1~n사이에 들어옴
  x = x + t *dr[d];
  
  printf("%d %d", x, d);
  return 0;
}