백준 10158번 개미 c++ 풀이

문제

가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.

 

위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (4,2), (3,1)로 움직인다. 

여러분은 크기 w×h인 격자 공간에서 처음에 (p,q)에서 출발하는 개미의 t시간 후의 위치 (x,y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다. 

문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다. 

입력

첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그 다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다. 

출력

출력은 t 시간 후에 개미의 위치 좌표 (x,y)의 값 x와 y를 공백을 사이에 두고 출력한다. 

예제 입력 1 복사

6 4
4 1
8

예제 출력 1 복사

0 1

예제 입력 2 복사

6 4
5 3
4

예제 출력 2 복사

3 1

 

이게 왜 실버3 밖에 되지 않는걸까? ㅋㅋㅋ 어렵다

 

단순한 구현 문제인줄 알았으나 시간 초과 기준이 0.15초이다. t는 2억이기 때문에 절대 시간 제한 안에 못풀 것 같아서 답지를 참고했다.

이 문제에서 개미가 움직일 수 있는곳은 한정되어 있다. 45도씩 움직이다보면 반복되는 위치가 생기기 때문에 그것을 이용해서 문제를 풀 수 있게 된다. 현재 개미의 위치에서 t초를 더해주고 각각의 p,q에 가로 세로를 2배로 늘린  w * 2 ,  h * 2를 나눈 나머지를  구해준다면 값이 w 또는 h 보다 크다면 다시 돌아오고 있는 것이고 적다면 앞으로 나아가고 있는 것이 된다. 따라서 다시 돌아오고 있다면 p - w * 2, q - h * 2를 해 주게 된다면 개미의 현재 위치를 구할 수 있다고한다. 아직 완벽하게 이해가 되지는 않았다.. 어렵다 어려워

 

#include <bits/stdc++.h>

using namespace std;

int w, h, p, q, t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> w >> h >> p >> q >> t;

    p += t;
    q += t;

    p %= w * 2;
    q %= h * 2;

    if(p > w) p = w * 2 - p;
    if(q > h ) q = h * 2 - q;

    cout << p << " " << q << "\n";



}