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

 

* 접근 방법
- 주어진 표에서 규칙을 아래와 같이 찾아봄
- 규칙을 찾은 후, 방법 1과 방법 2를 생각해냈고 방법 1은 if문이 많이 필요할 것 같아 2번을 이용해 보기로 함

 

* 1번 방법

#include <iostream>
using namespace std;

int main()
{
	long long int T = 0, n = 1, a = 1, b = 1;
	cin >> T;
	
	for (int i = 1; i < T; i++)
	{
		if (n % 2 != 0)
		{
			if (a != 1)
				a--;
			else
				n++;	// 층 수 증가
			b++;
		}
		else
		{
			a++;
			if (b != 1)
				b--; 
			else
				n++;	// 층 수 증가
		}
	}
	cout << a << "/" << b;

	return 0;
}

- 각 층의 마지막 숫자임을 어떻게 알아낼 것인가가 고민이었는데,
  홀수층의 마지막 숫자는 a가 1이고, 짝수층의 마지막 숫자는 b가 1임을 이용하였음

 

* 2번 방법

#include <iostream>
using namespace std;

int main()
{
	long long int T = 0, n = 1, p = 0;
	cin >> T;
	
	while (1)
	{
		if (n*(1 + n) / 2 >= T)		// 몇 층?(등차1인 등차수열 합)
		{
			if (T != n * (1 + n) / 2)			// 몇 번째?
			{
				p = T - (n - 1) * n / 2;
			}
			else
				p = n;

			break;
		}
		n++;
	}

	if (n % 2 == 0)
		cout << p << "/" << n - p + 1;
	else
		cout << n - p + 1 << "/" << p;

	return 0;
}

- 부등식을 만족하는 해를 찾는 건 언제해도 헷갈린다..