문제 설명
가로 길이가 w, 세로 길이가 h인 직사각형 격자 안에서 개미 한 마리가 이동한다.
처음 위치는 (p, q)이고, 개미는 매 시간마다 오른쪽 위 45도 방향으로 한 칸씩 이동한다.
이동하다가 경계에 부딪히면 반사되어 같은 속력으로 방향을 바꿔 계속 이동한다.
주어진 시간 t 후, 개미의 위치를 구하는 문제이다.
입력
첫째 줄: 격자의 크기
w h둘째 줄: 개미의 시작 위치
p q셋째 줄: 이동 시간
t출력
t시간 후 개미의 위치 (x, y)를 공백으로 구분해 출력한다.
입력 예시
6 4
4 1
8출력 예시
0 1문제 해결 아이디어
처음에는 개미가 한 칸씩 움직이며 벽에 닿을 때마다 방향을 바꾸는 식으로 시뮬레이션을 떠올릴 수 있다.
하지만 t의 범위가 매우 크다.
1 ≤ t ≤ 200,000,000즉, 매 초마다 직접 움직이면 시간초과가 날 가능성이 크다.
이 문제의 핵심은 반사 운동을 규칙으로 바꿔 계산하는 것이다.
핵심 관찰
가로 방향만 따로 생각해 보면, 개미는
0 → w → 0 → w처럼 반복해서 왕복한다.
세로 방향도 마찬가지로
0 → h → 0 → h처럼 움직인다.
즉, x축과 y축을 각각 독립적으로 계산할 수 있다.
규칙 정리
예를 들어 x축에서 startX + time만큼 이동했다고 생각해 보자.
이 값이 x를 몇 번 왕복했는지에 따라 위치가 달라진다.
1. 짝수 번째 구간
정방향으로 이동 중이므로
(startX + time) % x가 현재 위치가 된다.
2. 홀수 번째 구간
반대 방향으로 이동 중이므로
x - ((startX + time) % x)가 현재 위치가 된다.
세로 방향도 똑같이 계산할 수 있다.
강의 풀이
강의에서는 이 규칙을 그대로 식으로 구현했다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int startX = Integer.parseInt(st.nextToken());
int startY = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(br.readLine());
if((startX + time) / x % 2 == 1)
System.out.print(x - (startX + time) % x);
else
System.out.print((startX + time) % x);
if((startY + time) / y % 2 == 1)
System.out.print(" " + (y - (startY + time) % y));
else
System.out.print(" " + ((startY + time) % y));
}
}내가 작성한 풀이
내 코드도 계산 로직은 강의 코드와 동일하게 작성했다.
코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
int startX = sc.nextInt();
int startY = sc.nextInt();
int time = sc.nextInt();
if((startX + time) / x % 2 == 1)
System.out.print(x - (startX + time) % x);
else
System.out.print((startX + time) % x);
if((startY + time) / y % 2 == 1)
System.out.print(" " + (y - (startY + time) % y));
else
System.out.print(" " + ((startY + time) % y));
}
}왜 내 코드는 시간초과가 났을까
계산 로직은 같지만, 입력 방식에서 차이가 있었다.
| 방식 | 특징 |
|---|---|
| Scanner | 사용은 편하지만 상대적으로 느림 |
| BufferedReader + StringTokenizer | 빠른 입력 처리 가능 |
이 문제는 시간 제한이 매우 짧다.
0.15초그래서 로직이 같아도 Scanner를 사용하면 시간초과가 날 수 있다.
즉, 이 문제에서 중요한 것은 단순히 알고리즘뿐 아니라
입력 처리 속도도 함께 고려해야 한다는 점이다.
핵심 개념
1. 반사 운동을 왕복 패턴으로 보기
직접 방향을 바꾸며 시뮬레이션하지 않고,
가로와 세로를 각각 독립적인 왕복 운동으로 본다.
2. 홀수 구간 / 짝수 구간 판단
(start + time) / 길이를 통해 몇 번째 구간에 있는지 판단할 수 있다.
- 짝수 구간: 정방향
- 홀수 구간: 역방향
3. 나머지 연산 활용
현재 구간 안에서의 위치는
(start + time) % 길이로 구할 수 있다.
4. 빠른 입력 처리
시간 제한이 매우 짧은 문제에서는
BufferedReader + StringTokenizer조합을 우선적으로 고려하는 것이 좋다.
시간 복잡도
이 풀이의 시간 복잡도는
O(1)이다.
반복문 없이 몇 번의 사칙연산만으로 결과를 구할 수 있기 때문이다.
정리
이 문제는 처음 보면 개미의 이동을 직접 시뮬레이션해야 할 것 같지만,
실제로는 반사 운동을 왕복 패턴으로 바꿔 생각하면 수식으로 해결할 수 있는 문제였다.
또한 내 코드는 강의 코드와 로직은 같았지만,
입력 방식에서 Scanner를 사용해 시간초과가 발생했다.
이번 문제를 통해
- 반사 이동 문제를 규칙으로 단순화하는 방법
- 나머지 연산을 활용한 위치 계산
- 빠른 입력의 중요성
을 함께 배울 수 있었다.
