분수찾기 (feat. 백준, 1193번)

분수찾기
https://www.acmicpc.net/problem/1193

1193번: 분수찾기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1193
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int X, s = 1, e = 1, floor = 1;
	cin >> X;
	while (true) {
		if (s <= X && X <= e)
			break;
		s += floor;
		e += (floor + 1);
		++floor;
	}
	if (floor & 1)
		cout << (s - X + floor) << "/" << (X - e + floor) << endl;
	else
		cout << (X - e + floor) << "/" << (s - X + floor) << endl;
	return 0;
}
// *&)*@*

다음과 같은 피라미드가 있다고 가정해보겠습니다.

이 피라미드는 규칙이 있습니다. 바로 자신의 층이 해당 층의 값에 반영된다는 것인데요.

각 층의 시작점은 1/나의 층, 끝점은 나의층/1 입니다. 해당 피라미드에 문제의 값을 아래와 같이 대입시켜봅니다.

문제로 주어진 숫자에 해당하는 정답이 동일한 것을 알 수 있습니다. 다만 3->4로 넘어갈때처럼 숫자는 피라미드의 시작점부터 채워지지 않고 지그재그로 채워진다는 것을 알 수 있습니다.