Boj 5014) 스타트링크

문제

백준 5014

설명

이 문제는 Ux + Dy = gcd(U, D) 의 해를 구하는 확장 유클리드 알고리즘 문제가 될 뻔 했다. 하지만 천장과 바닥이란 한계가 주어져서 수식으로 풀기엔 경우의 수가 많고 주어진 범위도 작아서 시뮬레이션을 돌리는게 맘이 편하다. 어떻게 시뮬을 돌릴까?

BFS 를 써서 0 ~ 1000000 범위에 대해서 탐색을 하는 것이 한 방법이다.

다른 방법으로는 Griddy 전략을 이용한다. 목적지보다 윗칸에 있으면 아래층으로 가고, 목적지보다 아래칸에 있으면 위층으로 가는 간단한 전략이다. 만약 도착지에 갈 수 있다면(Ux + Dy = gcd(U, D) 의 해가 있다면) 최대 1000000 번 내에 도착할 것이다.

여기에 추가로 천장을 못뚫고 지하를 못뚫도록 조건문을 추가해둔다. 그러면 제한이 없었다면 원래 도착지에 갈 수 있었던 일부 경우에서 무한 루프를 돌 것이다. 어차피 반복문의 상한을 정해놨기 때문에 실제로 무한으로 돌진 않는다.

그래서 나온 것이 아래 코드이다. 나는 생각해내기 어려웠어서 기록한다.

시간 복잡도

O(\(N\))

코드

int main()
{
	int F, S, G, U, D;
	cin >> F >> S >> G >> U >> D;

	// Ux + Dy = d 의 해가 있는제 체크. 없어도 정답과는 영향 없음
	int d = gcd(U, D);
	if (d == 0 || abs(G - S) % d) {
		cout << "use the stairs";
		return 0;
	}

	for (int i = 0; S >= 1 && S <= F && i <= F; i++)
	{
		if (S == G)
		{
			cout << i; return 0;
		}
		if (S > G && S - D > 0 || (S + U>F)) S -= D;
		else  S += U;
	}

	cout << "use the stairs";
}