[C++] 백준 1193번: 분수찾기

문제 바로가기

문제에서 주어진 표는 다음과 같다.

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

각 대각선에서 분모는 ↗ 방향으로 증가하고, 분자는 ↙ 방향으로 증가한다.

주어진 표에서 방문 순서대로 값을 메기면,

1	2	6	7	15	…
3	5	8	14	…	…
4	9	13	…	…	…
10	12	…	…	…	…
11	…	…	…	…	…
…	…	…	…	…	…

사실 나는 문제를 제대로 읽지 않아, 아래처럼 생각했었다.

1	2	4	7	11	…
3	5	8	12	…	…
6	9	13	…	…	…
10	14	…	…	…	…
15	…	…	…	…	…
…	…	…	…	…	…

하지만 결정적으로 이러한 실수가 답을 해결하는데 큰 도움이 됐다.

맨 윗줄을 차례대로 보면, 누적합이 된다는 것을 알 수 있다.

$${1, 1+1, 1+1+2, 1+1+2+3, 1+1+2+3+4, ... }$$

따라서 X가 주어졌을 때 이 수보다 큰 누적합 중 제일 작은 수가 있는 대각선이 X가 있는 대각선인 것이다.

즉, $$ X ≥ S=1+\sum_{n=1}^{i}{n} $$를 만족하는 i와 S를 알면 답을 구할 수 있다.

그리고 대각선에서 몇 번째인지를 알려면, \(S - X\)를 통해 ↙방향(또는 ↗방향) 순서를, \(S + i - X\)를 통해 ↗방향(또는 ↙방향) 순서를 알 수 있다. 매 대각선마다 방향을 반대로 적용해주면 된다.

아래는 코드 전문이다.

#define EL "\n"

#include <iostream>

using namespace std;

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

	int X;
	cin >> X;

	int i = 0;
	int sum = 1;
	while (sum + i <= X) {
		sum += i;
		i++;
	}

	if (i % 2 == 0)
		cout << X - sum + 1 << "/" << sum + i - X << EL;
	else
		cout << sum + i - X << "/" << X - sum + 1 << EL;

	return 0;
}