[C++/8891] 점 숫자

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

휴가를 알차게 보내고 오느라 모든걸 놓고 놀았습니다. 휴가 복귀후에 감이 떨어졌나 확인할 겸 쉬운 문제 하나 풀어봤습니다. 문제 고르는 능력이 좀 부족하다고 생각이 됩니다. 고를때마다 처음보는 유형인 문제를 고르는 것 같습니다.

어쨌든, 해당 문제는 아래와 같이 풀었습니다.

한줄을 레벨이라고 표현해보겠습니다. 한 레벨이 늘어날 때마다 1개 2개 3개 4개 ... n - 1개 n개로 늘어나는 것을 먼저 파악했습니다. 총 개수가 계속해서 늘어나고 있으며, 마지막 숫자는 그 레벨의 마지막 값이 될 것입니다.

그리고 위 내용을 저장하는데, 배열을 사용했습니다. 배열의 인덱스에 맞춰서 1은 마지막 숫자 1,  2는 마지막 숫자 3 3은 마지막 숫자 6으로 측정이 됩니다. 

이제 이런 내용을 프로그램을 시작할때 미리 만들어 두는 겁니다. 인덱스는 알아서 생겨날 것이고, 숫자는 누적합이니까 계속해서 더해가면서 메모제이션을 해주면 될 것입니다. 그리고 숫자가 10,000보다 작다곤 하지만, 10,000과 9,999로 된다면? 그 값은 더욱 커져 10,000까지만 하는 것이 아니고 이왕이면 큰 값을 해주면 됩니다. 저는 100,000으로 했지만 아마 계산을 하면 더욱 줄일 수 있을 것 같습니다.

이제 저 방식으로 생성된 dp 배열을 두고 문제를 해결하면 됩니다.

첫번째 숫자와 두번째 숫자가 주어질때, 각 좌표를 구하면 됩니다. 

1번 인덱스부터 순회를 하면서 해당 dp[idx]값이 숫자보다 크거나 같을때를 찾아 숫자와 인덱스를 구해놓고, 숫자를 하나씩 줄여나가면서 좌표를 이동시킵니다. 그렇게 좌표를 구할 수 있습니다.

이제 좌표가 나온 것을 합쳐서 해당 좌표에 있는 숫자가 무엇인지 파악합니다.

dp배열에 저장되어있는 값들은 1열에 위치해 있고, 해당 위치는 x,y좌표를 합한것에서 1을 빼주면 됩니다. 그 이유는 무엇이냐면? 해당 좌표의 합이 똑같은 레벨에 위치해있기 때문입니다.

예를 들어서 5가 위치한 곳은 (2,2)인데 그 레벨에 있는 값들의 좌표의 합은 항상 4입니다. 그리고 0부터 시작이 아닌 1부터 시작이기 때문에 두 좌표의 합에서 1을 제외해주면 해당 좌표가 위치하는 레벨로 찾아갈 수 있게 됩니다.

그렇게 좌표를 구하고, 숫자를 구하게 된다음, 해당하는 좌표를 찾을때까지 돌아주면 그 숫자가 나오게 됩니다. 이해가 안될수도 있습니다. 왜냐하면 즉흥으로 쓴 글이기 때문입니다. 아래의 코드를 보시면 약간이나마 이해가 될 것입니다. 아래는 정답코드입니다.

//https://www.acmicpc.net/problem/8891

#include<iostream>
#include<cstring>

#define MAX 10001
using namespace std;

int idx,dp[MAX],testCase,firstDot,secondDot;

void memozation() {
	
	memset(dp,0,sizeof(dp));
	
	idx = 1;
	int number = 1;
	
	while(1) {
		
		dp[idx] = dp[idx - 1] + number;
		
		if(dp[idx - 1] + number > 50000) break;
		
		idx++;
		number++;
		
	}
	
}

pair<int,int> findCoor(int number) {
	
	int startIdx = 0;
	int startNumber = 0;
	
	for(int i = 1; i <= idx; i++){
		if(number <= dp[i]){
			startNumber = dp[i];
			startIdx = i;
			break;
		}
	}
	
	//cout << "start number : " << startNumber << " " << "start idx : " << startIdx << "\n";
	
	pair<int,int> coor = {1,startIdx};
	
	while(number != startNumber) {
		startNumber--;
		coor.first += 1;
		coor.second -= 1;
	}
	
	//cout << "coor : " << coor.first << " " << coor.second << "\n";
	
	return coor;
}

int findResult(int f, int s) {
	
	
	int firstTemp = 1;
	int secondTemp = f + s - 1;
	int number = dp[secondTemp];
	
	
	while(f != firstTemp && s != secondTemp){
		firstTemp++;
		secondTemp--;
		number--;
	}
	
	return number;
}

int main() {
	
	memozation();
	
	cin >> testCase;
	while(testCase--){
		
		cin >> firstDot >> secondDot;
		
		pair<int,int> firstCoor = findCoor(firstDot);
		pair<int,int> secondCoor = findCoor(secondDot);
		pair<int,int> result = {firstCoor.first + secondCoor.first, firstCoor.second + secondCoor.second};
		
		cout << findResult(result.first, result.second) << "\n";
		
	}
	
	
	return 0;
}