취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2155번 문제인 삼각형의 최단 경로이다.
문제는 아래 링크를 확인하자.

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

입력으로 주어지는 두 수중 작은 수를 A, 큰 수를 B라 하자.

작은 수의 위치부터 (큰 수와 같은 행에 있게 될 때까지 한 행씩 내려간 위치)를 왼쪽 아래와 오른쪽 아래방향으로 각각 찾고, 같은 행에서는 좌우로 움직여야하는 횟수를 구해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <utility>
using namespace std;

int A, B;
int floorA, floorB;
int ll, rr;
int dist = 0;

int floor(int x) {
	int L = 1, R = 31663;
	while (L < R) {
		int mid = (L + R) / 2;
		if (mid * mid >= x) R = mid;
		else L = mid + 1;
	}

	return L;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> A >> B;
	if (A > B) swap(A, B);

	floorA = floor(A), floorB = floor(B), ll = A, rr = A;

	while (floorA < floorB) {
		if ((ll & 1) == (floorA & 1)) {
			ll += floorA * 2, rr += floorA * 2;
			floorA++;
		}
		else {
			ll--, rr++;
		}
		dist++;
	}

	if (B < ll) cout << dist + (ll - B);
	else if (rr < B) cout << dist + (B - rr);
	else {
		if ((ll & 1) == (B & 1)) cout << dist;
		else cout << dist + 1;
	}
}