백준 - 영재의 산책(19953번)

 문제

t 가 10억이므로 매 초마다 이동해주면 시간 초과가 날 수 밖에 없다.

(v * m) % 10 의 규칙을 활용해야 한다.

여러 수를 대입해 본 결과 v, m 이 어떤 조합이던 간에 결과 값은 4개의 패턴만을 가진다.

v = 1, m = 2 일 때 -> 2, 4, 8, 6

v = 123, m = 127 일 때 -> 1, 7, 9, 3

즉, 맨 처음 북쪽으로의 이동을 제외하면 다음 이동부터는 동, 서, 남, 북 네 방향으로의 이동 거리가 일정하다는 뜻이다.

처음 북쪽으로 이동한 뒤 그 지점을 시작점으로 잡고, 동, 서, 남, 북으로 각각 몇 번 갈 수 있는지 구한 뒤

이동 거리만큼 계산해주면 된다.

	#include<iostream>
	#include<memory.h>
	#include<algorithm>
	#include<math.h>
	#include<string>
	#include<vector>
	#include<stack>
	#include<queue>
	#include<map>
	#include<set>
	using namespace std;
	#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
	#define pii pair<int, int>
	#define pdd pair<double, double>
	#define pic pair<int, char>
	#define ll long long
	#define pll pair<ll, ll>
	#define vi vector<int>
	#define vl vector<long long>
	#define vc vector<char>
	#define vii vector<pii>
	#define IMAX 2000000001
	#define LMAX 1000000000000000000
	#define DMAX 0xFFFFFFFFFFFFF
	#define MOD 100003
	int mv1[4] = { 0, 1, 0, -1 };
	int mv2[4] = { 1, 0, -1, 0 };
	int mv_all1[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };
	int mv_all2[8] = { 1, 0, -1, 0 , -1, 1, -1, 1 };
	int v, m, t;
	int dv[4];
	int cnt[4];
	int main(void) {
	FIO;
	cin >> v >> m >> t;
	int num = (v * m) % 10;
	for (int i = 0; i < 4; i++)
	{
	dv[i] = num;
	num = (num * m) % 10;
	}
	int x = 0, y = v;
	t--;
	for (int i = 0; i < 4; i++)
	{
	cnt[i] = (t - 1) / 4;
	}
	for (int i = 0; i <= (t - 1) % 4; i++)
	{
	cnt[i]++;
	}
	x += dv[0] * cnt[0] - dv[2] * cnt[2];
	y += dv[3] * cnt[3] - dv[1] * cnt[1];
	cout << x << " " << y;
	}

view raw 19953_영재의 산책.cpp hosted with ❤ by GitHub