10158)개미

https://www.acmicpc.net/problem/10158

가로 길이가 w, 세로 길이가 h인 격자 공간에 (p,q)에 개미를 두면 1시간 후에 개미는 (p+1,q+1)으로 이동한다.

개미가 격자 공간의 경계에 부딪히면 운동방향이 바뀐다.

이것을 쉽게 표현하기 위해 개미는 한 시간 뒤에 (p+dx, q+dy)로 이동한다고 하자. (초기 dx = 1, dy = 1)

개미가 x = 0, x = w에 부딪힐 때 x축 이동 방향이 반대로 바뀐다.

예를들어 개미의 이동 방향이 dx = 1, dy = -1일 때 x = w에 부딪히면 dx = -1, dy = -1로 바뀐다.

개미가 y = 0, y = h에 부딪힐 때 y축 이동 방향이 반대로 바뀐다.

#include<stdio.h>
 
int main() {
    int w, h;
    int p, q;
    int t;
    int dx = 1, dy = 1;
 
    scanf("%d %d", &w, &h);
    scanf("%d %d", &p, &q);
    scanf("%d", &t);
 
    for (int i = 0; i < t;i++) {
        if (p == 0 || p == w) {
            if (dx > 0) dx = -1;
            else dx = 1;
        }
        if (q == 0 || q == h) {
            if (dy > 0) dy = -1;
            else dy = 1;
        }
 
        p += dx, q += dy;
    }
    printf("%d %d\n",p,q);
 
    return 0;
}

이렇게 풀면 대단히 시간이 많이 걸린다.

그래서 다른 사람이 작성한 코드를 보면서 어떻게 효율적으로 코드를 짤 수 있을까 공부했는데

참 좋은 아이디어가 있어서 정리하려고 한다.

출처 : https://hanstemcell.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EA%B0%9C%EB%AF%B8?category=672485

개미는 x,y 방향으로 이동하기 때문에 잘 몰랐지만 x방향 이동과 y방향 이동으로 나뉜다.

문제를 조금 더 쉽게 이해하기 위해 x방향 이동만 생각해보자.

그럼 개미는 시간 t동안 0~w까지 왕복 이동한다는 것을 알 수 있다.

p+t는 개미가 t동안 총 이동한 거리를 뜻하는데 여기에 w를 나누면 개미가 0~w까지 몇 번 왕복했는지 알 수 있다.

그렇다면 t이후에 개미의 위치는 어디일까?

이 값은 (p+t)/w가 짝수인가 홀수인가에 따라 다르다.

이 값이 짝수이면 x=0에서 출발해 (p+t)%w인 곳에 개미가 위치하고

이 값이 홀수이면 x=w에서 출발해 -(p+t)%w인 곳에 개미가 위치한다.

y방향 이동도 비슷하게 구하면 된다.

#include<stdio.h>
 
int main() {
    int w, h;
    int p, q;
    int t;
    int a, b;
    int x, y;
 
    scanf("%d %d", &w, &h);
    scanf("%d %d", &p, &q);
    scanf("%d", &t);
 
    a = (p+t)/w, b = (q+t)/h;
    
    if (a%2 == 0) x = (p+t)%w;
    else x = w-(p+t)%w;
    if (b%2 == 0) y = (q+t)%h;
    else y = h-(q+t)%h;
 
    printf("%d %d\n", x, y);
 
    return 0;
}