# 달팽이

# 문제

 

# 입력 및 출력

 

# 풀이

처음에 N, N-1, N-1, N-2, N-2, ... , 2, 2, 1, 1 이 값을 빼주는 작업이 시간 초과가 걸릴 것이라고 생각했다.

왜냐하면 N이 10^7으로 매우 큰 상태기 때문이다.

근데 막상 보면 N^2번 반복되는 작업이 아니고 N번 반복되는 작업이기 때문에

시간초과는 걸리지 않는다.

 

엄청 복잡하게 풀어서 알고리즘을 천천히 글로 정리해봤다.

글로 쓰고 나니까 머릿속에 정리가 되는 느낌이다.

#include <fstream>
using namespace std;

long long N;
long long dx[4] = { 0,1,0,-1 };
long long dy[4] = { 1,0,-1,0 };

ifstream fin("snail.inp");
ofstream fout("snail.out");

// K, R 찾기
pair<long long, long long> find_range(long long a) {
	long long n = N;
	long long cnt = 0; // K
	while (a >= n) {
		cnt++, a -= n;
		if (n == N) {
			n--;
			continue;
		}
		if (a < n || n <= 0) break;
		cnt++, a -= n;
		n--;
	} // R = a
	return make_pair(cnt, a); // (K, R) 리턴
}

// 실제 인덱스 찾기
pair<long long,long long> find_index(pair<long long, long long> sr) {
	pair<long long, long long> result;
	long long s = sr.first / 4; // s
	long long r = sr.first % 4; // r
	switch (r) {
		case 0:  
			result = make_pair(s + 1, s);
			break;
		case 1:
			result = make_pair(s + 1, N - s);
			break;
		case 2:
			result = make_pair(N - s, N - s);
			break;
		default:
			result = make_pair(N - s, s + 1);
			break;
	}
	// 찾고자 하는 인덱스에 도달하기 전 달팽이가 마지막으로 회전하는 위치 찾음

	for (long long i = 0; i < sr.second; i++) {
		result.first += dx[r];
		result.second += dy[r];
	}
	// 오, 아래, 왼, 위 중 정해진 방향으로 R 만큼 이동
    
	return result; // 실제 위치 리턴
}

void snail(long long A, long long B) {
	pair<long long, long long> a, b, res_a, res_b;
	a = find_range(A);
	b = find_range(B);
	res_a = find_index(a); // a의 실제 인덱스
	res_b = find_index(b); // b의 실제 인덱스
    
    // 절대값 abs 함수가 오류날 것 같아 직접 확인해줌
	long long check = ((res_a.first - res_b.first) == (res_a.second - res_b.second)) ||
		((res_a.first - res_b.first) == (-1)*(res_a.second - res_b.second)); 
    
    // 정답 출력
	if (check) fout << "YES" << "\n";
	else fout << "NO" << "\n";
}

int main() {
	int T;
	fin >> T;
	while (T--) {
		long long A, B;
		fin >> N >> A >> B;
		snail(A, B);
	}
	fin.close();
	fout.close();
}

 

 

확실히 N이 커서 그런지 시간이 오래걸리긴 했다.

그래도 꽤 복잡한 알고리즘인데 혼자 힘으로 한 번에 맞춰서 기분이 좋다.ㅎㅎ

 

내가 어렵게 푼 걸까?