[BOJ 10436 // C++] 무한 유리수 트리

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

 

이번에 볼 문제는 백준 10436번 문제인 무한 유리수 트리이다.
문제는 아래 링크를 확인하자.

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

10436번: 무한 유리수 트리

주어지는 유리수가 한 층의 맨 오른쪽 원소인 경우의 해는 간단히 구할 수 있다. 그렇지 않은 경우, 트리 위에서 다음과 같이 움직이는 것으로 항상 다음 유리수를 찾을 수 있다:

 

(1) 왼쪽 위로 최대한 올라간다. 이때 그 올라간 횟수를 k회라 하자

(2) 오른쪽 위로 한 칸 올라간다.

(3) 오른쪽 아래로 한 칸 내려간다.

(4) 왼쪽 아래로 k회 내려간다.

 

1~4의 각 움직임은 간단한 사칙연산을 이용한 수식으로 표현할 수 있다. 이를 이용해 문제를 해결하자.

 

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

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

ll P, T, X, Y;
string s;

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

	cin >> P;
	while (P--) {
		cin >> T >> s;
		int idx = 0;
		while (s[idx] != '/')idx++;
		X = stoll(s.substr(0, idx)), Y = stoll(s.substr(idx + 1, s.length() - idx - 1));

		if (Y == 1) cout << T << ' ' << 1 << '/' << X + 1 << '\n';
		else {
			ll cnt = X / Y;
			X = X % Y;
			Y -= X;
			X += Y;
			Y += X * cnt;

			cout << T << ' ' << X << '/' << Y << '\n';
		}
	}
}