[java][boj][s4] 10158. 개미

10158번: 개미

문제

가로 길이가 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. 가로 w 세로 h
 * 2. 초기 위치의 좌표 p q
 * 3. 개미가 움직일 시간 t
 * 출력
 * 1. t시간 후 개미의 위치 좌표 x y
 * 조건
 * 1. 한 시간마다 p+1, q+1로 움직임
 * 2. 경계면에 부딪치면 같은 속력으로 반사
 */

메모리 초과에 시간 초과까지 난리였다... 처음에는 1부터 T까지 for문을 돌렸는데 당연하게도 시간 초과가 났고, 그 다음에는 while문을 써서 T를 건너뛰는 식으로 구현을 했지만 이것 또한 시간 초과가 났다

 

결론은 이 문제를 풀기 위해서는 구현이 아니라 수학 계산을 해야 했다

시간 - (가로 길이 - 현재 위치)를 가로 길이로 나누면 가로 길이를 한 번 이동하는 게 총 몇 번인지 나오는데, 이것은 계산하지 않아도 된다 어차피 한 바퀴를 순환하면 다시 제자리로 돌아오기 때문에..

대신 나누기 2를 해서 짝수가 나온다면 가로 길이의 끝에서부터 남은 이동을 해야 하고, 홀수라면 0에서부터 남은 이동을 하면 된다

남은 이동은 시간 - (가로 길이 - 현재 위치)를 가로 길이로 남은 나머지이다 따라서

p = w-(T-(w-p)%w) or T-(w-p)%w가 현재 위치가 된다 q도 변수만 바꿔 주면 된다

코드

package com.ssafy.boj;

import java.io.*;
import java.util.*;

public class s4_10158_개미 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int w = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int p = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		int T = Integer.parseInt(br.readLine());
		
		int T1 = T-(w-p);
		int T2 = T-(h-q);
		
		if(T1>=0) {
			if((T1/w)%2 == 0) p = w-(T1%w);
			else p = T1%w;
		} else p = p+T;
		
		if(T2>=0) {
			if((T2/h)%2 == 0) q = h-(T2%h);
			else q = T2%h;
		} else q = q+T;

		System.out.println(p + " " + q);

	}

}

결과

 

아래에 for문과 while을 이용한 알고리즘도 첨부한다

 

//while을 이용한 알고리즘

package com.ssafy.boj;

import java.io.*;
import java.util.*;

public class s4_10158_개미2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int w = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int p = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		int T = Integer.parseInt(br.readLine());
		
		int dx = 1;
		int dy = 1;
		int t = 0;
		int min = Integer.MAX_VALUE;
		int dir = 0;
		
		while(true) {
			if(t>=T) break;
			else if(dx==1 && dy==1) {
				dir = 1;
				if(w-p <= h-q) dx *= (-1);
				if(w-p >= h-q) dy *= (-1);
				min = Math.min(w-p, h-q);
				t += min;
				p += min;
				q += min;
			}
			
			else if(dx==-1 && dy==1) {
				dir = 2;
				if(p <= h-q) dx *= (-1);
				if(p >= h-q) dy *= (-1);
				min = Math.min(p, h-q);
				t += min;
				p -= min;
				q += min;
			}
			
			else if(dx==1 && dy==-1) {
				dir = 3;
				if(w-p <= q) dx *= (-1);
				if(w-p >= q) dy *= (-1);
				min = Math.min(w-p, q);
				t += min;
				p += min;
				q -= min;
			}
			
			else if(dx==-1 && dy==-1) {
				dir = 4;
				if(p <= q) dx *= (-1);
				if(p >= q) dy *= (-1);
				min = Math.min(p, q);
				t += min;
				p -= min;
				q -= min;
			}
		}
		
		if(t>T) {
			switch(dir) {
			case 1:
				p -= t-T;
				q -= t-T;
				break;
			case 2:
				p += t-T;
				q -= t-T;
				break;
			case 3:
				p -= t-T;
				q += t-T;
				break;
			case 4:
				p += t-T;
				q += t-T;
				break;
			}
		}
		
		System.out.println(p + " " + q);

	}

}

//for를 이용한 알고리즘

package com.ssafy.boj;

import java.io.*;
import java.util.*;

public class s4_10158_개미3 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int w = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int p = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		int T = Integer.parseInt(br.readLine());
		
		int dx = 1;
		int dy = 1;

		for(int t = 0; t<T; t++) {
			p = p+dx;
			q = q+dy;
			if(p==w || p==0) dx *= (-1);
			if(q==h || q==0) dy *= (-1);
			
		}
		
		System.out.println(p + " " + q);

	}

}

#자바 #java #boj #백준 #알고리즘