[백준] 1193번: 분수찾기

문제링크 : https://www.acmicpc.net/problem/1193

문제풀이

찾을 수 있는 규칙

1. 위의 표는 분자와 분모 합이 같은 것끼리 한 줄에 나열한 것이다.

2. 최대 분모는 순차적으로 늘어난다.

3. 최대 분모가 짝수일 때와 홀수일 때 분자 분모가 증가하는 모양이 서로 반대이다.

4. 분자와 분모가 1씩 증가, 감소한다.

그러면 우선, 입력받은 숫자의 최대 분모가 몇인지부터 알아야 한다.

각 줄의 제일 큰 수 (1, 3, 5, 10, 15 ...)로 비교를 하면 되겠다.

while (sum < N) {
	sum += ++max_denominator;
}

순차적으로 더하면서 입력받은 숫자의 최대 분모(max_denominator)가 몇인지, 그 줄의 제일 큰 수(sum)는 몇인지 알아낸다.

분모는 위에서 구한 최대 분모 값으로 설정하고, 분자는 1로 설정한다.

그 줄의 제일 큰 수(sum)부터 입력받은 값(N)까지 분모는 1씩 감소, 분자는 1씩 증가시킨다.

for (int i = sum; i > N; i--) {
	denominator--;
	numerator++;
}

예) 입력값이 14인 경우, sum은 15가 되고 최대 분모 값은 5가 된다.

그러면 for문을 돌면서 i가 14보다 클 때까지 분모는 감소, 분자는 증가되어 분모는 4, 분자는 2값이 된다.

마지막으로 위의 표를 보면 최대 분모값이 짝수일 때와 홀수일 때 커지는 순서가 다르다.

이를 위해 짝수인 경우에는 분자와 분모 값을 바꿔서 출력한다.

if (max_denominator % 2 == 0) {
	cout << denominator << '/' << numerator;
}
else {
	cout << numerator << '/' << denominator;
}

소스코드

/*
 * 백준 1193번: 분수찾기
 */

#include <iostream>

using namespace std;

int main() {
	int N;
	cin >> N;

	int sum = 1;
	int max_denominator = 1;
	while (sum < N) {
		sum += ++max_denominator;
	}

	int denominator = max_denominator;	// 분모
	int numerator = 1;					// 분자

	for (int i = sum; i > N; i--) {
		denominator--;
		numerator++;
	}

	if (max_denominator % 2 == 0) {
		cout << denominator << '/' << numerator;
	}
	else {
		cout << numerator << '/' << denominator;
	}

	return 0;
}