[백준] 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/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

예제 입력 1 복사

14

예제 출력 1 복사

2/4

 

해답

#include<iostream>

class Fraction 
{
public:
	int numerator;		//분자
	int denominator;	//분모

	Fraction();
	int SumFraction();
};

Fraction::Fraction()
{
	numerator = 1;
	denominator = 1;
}

int Fraction::SumFraction()
{
	return numerator + denominator;
}

int main()
{
	int input;
	std::cin >> input;

	if (input == 1)
	{
		std::cout << 1 << '/' << 1 << std::endl;
		return 0;
	}

	Fraction fraction;
	int sum_group = 3;		//분자 분모 합
	int num = 2;				//몇번째 숫자인지 알려주는 변수
	bool up = 0;				//지그재그 방향을 가르켜 주는 변수

	while (1)
	{
		
		for (int i = 0; i < sum_group - 1; i++)
		{
			if (up==1)								//지그재그 올라갈때
			{
				if (i == 0)						//첫번째로 바뀌는 값은 분자만 1증가
				{
					fraction.numerator++;
				}
				else                           //그외의 상황들은 분자 1 감소 분모 1 증가
				{
					fraction.numerator--;
					fraction.denominator++;
				}
			}
			else                               //지그재그 내려갈때
			{
				if (i == 0)						//첫번째로 바뀌는 값은 분모만 1증가
				{
					fraction.denominator++;
				}
				else							//그외의 상황들은 분자 1증가 분모 1감소
				{
					fraction.numerator++;
					fraction.denominator--;
				}
			}
			if (input == num)
			{
				std::cout << fraction.numerator << '/' << fraction.denominator << std::endl;
				return 0;
			}
			num++;
		}
		sum_group++;
		up = !up;
	}
}

수학문제에서는 규칙을 찾는게 중요하다. 코드가 조금 더럽지만 그래도 알맞은 규칙으로 문제를 풀어봤다.