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

문제 : www.acmicpc.net/problem/1193

 

<풀이>

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int input;
	cin >> input;
	int N = (-1 + (sqrt(1 + 8 * input)))/(2); // 근의 공식 사용
	int sumN = ((N * (N + 1)) / 2); // N의 합
	int ascN, descN;
	if (input == sumN) { ascN = 1; descN = N; }
	else { ascN = input - sumN; descN = N + 2 - ascN; }

	if (N % 2 != 0) { printf("%d/%d", ascN, descN); }
	else  { printf("%d/%d", descN, ascN); }
	
	return 0;
}

<어떻게 풀었는가?>

알아보겠는가? 쨌든 이러고 품

 대각선으로 값을 나눈 뒤 1/1을 1파트, 1/2 2/1을 2파트, 3/1 2/2 1/3을 3파트······ 이렇게 나눌 경우 한 가지 규칙이 나타난다. 1, 3, 6, 10, 15 ······ '1부터 특정 정수까지의 합' 번째 숫자는 분모와 분자가 바뀌는 기준점이라는 것이다. 그래서 나는 근의 공식을 이용하여 입력받은 값에서 가장 가까운 임의의 정수 n까지의 합을 구했고 여기서의 n이 입력받은 값이 해당하는 파트 전 파트번호가 된다. (즉, 입력받은 값이 해당하는 파트는 n+1)

 파트번호를 구했다면 그 다음은 간단하다. 왜냐하면 우리가 찾으려는 분수의 분자와 분모는 1부터 해당 파트번호 n까지 내림차순정렬 또는 오름차순정렬한 것이기 때문이다. 파트번호가 홀수일 경우 내림차순/오름차순, 파트번호가 짝수일 경우 오름차순/내림차순이다.

+단계별 풀어보기-수학 1에 해당하길래 내가 아는 수학.. 근의 공식을 이용하여 푼 것인데 구글링해보니 다들 이렇게 풀지는 않더라...