백준 영재의 산책(19953)

영재의 산책

1. 힌트

1) 영재는 계속 오른쪽으로 회전하므로 $4$번 이동하면 원래의 방향으로 돌아옵니다.

2) 가장 처음 이동을 제외하면 $x$번째 이동에서 이동하는 거리는 $(v \times m ^ x)\ \%\ 10$입니다.

3) 양의 정수를 $x$번 제곱했을 때, 일의 자리만 확인한다면 다음과 같이 반복됩니다.

1 -> [1]
2 -> [2, 4, 8, 6]
3 -> [3, 9, 7, 1]
4 -> [4, 6]
5 -> [5]
6 -> [6]
7 -> [7, 9, 3, 1]
8 -> [8, 6]
9 -> [9, 1]

2. 접근

1) 수식으로 표현할 수 있을까?

가장 처음 이동할때의 속도를 $v_0$라고 합시다
$0$번째 이동 거리는 $v_0$입니다.
$1$번째 이동 거리 $v_1 = (v_0 \times m)\ \%\ 10$입니다.
$2$번째 이동 거리 $v_2 = (((v_0 \times m)\ \%\ 10) \times m)\ \%\ 10$입니다.
$3$번째 이동 거리 $v_3 = ((((v_0 \times m)\ \%\ 10) \times m)\ \%\ 10 \times m)\ \%\ 10$입니다.
나머지 연산은 맨 마지막에 한 번만 해줘도 되므로 주어진 식은 다음과 같이 정리할 수 있습니다.
$v_x = (v_0 \times m^x)\ \%\ 10$
그런데 양의 정수를 $x$번 제곱했을 때, 일의 자리만 확인한다면 다음과 같이 반복됩니다.

1 -> [1]
2 -> [2, 4, 8, 6]
3 -> [3, 9, 7, 1]
4 -> [4, 6]
5 -> [5]
6 -> [6]
7 -> [7, 9, 3, 1]
8 -> [8, 6]
9 -> [9, 1]

따라서 속도는 가장 처음을 제외하고 무조건 $1,\ 2,\ 4$주기로 반복되는 것을 알 수 있습니다.

2) 문제를 분해할 수 있을까?

속도가 $1,\ 2,\ 4$주기로 반복되는데 방향 또한 오른쪽으로 회전하기만 한다면 $4$주기로 원래 상태로 돌아옵니다. 최소 공배수는 $4$이므로 이동 성분 또한 $4$주기로 반복됩니다. 따라서 $t-1$을 주기인 $4$로 나눈 후에 성분을 한 번에 더해주고 $4$로 나눈 나머지 만큼 더해주면 됩니다.

3. 구현

public class Main {
	
	static final int[] dy = { 1, -1, 0, 0 };
	static final int[] dx = { 0, 0, -1, 1 };
	static final int[] dr = { 3, 2, 0, 1 };
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int v = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken()) - 1;
		int x = 0; int y = v; int d = 3;
		v = (v * m) % 10; 
		int[] px = new int[5]; int[] py = new int[5];
		for (int i = 1; i <= 4; i++) {
			px[i] = v * dx[d]; py[i] = v * dy[d]; d = dr[d];
			px[i] += px[i - 1]; py[i] += py[i - 1];
			v = (v * m) % 10;
		}
		x += t / 4 * px[4]; y += t / 4 * py[4];
		x += px[t % 4]; y += py[t % 4];
		System.out.printf("%d %d\n", x, y);
	}

}