[백준] 1193 with C++

문제설명

---

입출력 예제

---

개념

　분수의 규칙을 이용해 n번 째 위치의 분수는 어떤 값인지 추측하는 문제다. 현재 값을 기준으로 증감의 규칙을 추론하여 다음 값을 추측하는 방법이 있고, 입력받은 정수의 위치를 추론하여 접근할 수 있는 방법이 있다.

 

분수의 규칙

---

풀이

풀이(1) 증감폭 이용

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	int num;
	cin >> num;
	int i = 0;
	int x = 1, y = 1;

　정수를 입력받고, x/y 꼴로 출력되는 변수 x와 y를 각각 1로 초기화해 준다. 그리고 반복의 횟수를 결정하는 변수 i도 0으로 초기화해 준다.

 

	while (i < num)
	{
		int an = round(sqrt(2 * i)); // 현재
		int bn = round(sqrt(2 * (i + 1))); // 다음

　i가 num보다 작을 때만 반복을 돌리는데, 위에 캡처되어 있는 <분수의 규칙> 사진을 다시 보자.

 

분수의 규칙

 

　분자/분수라고 다음 형태를 정의하였을 때, (분모 감소, 분자 증가)와 (분모 증가, 분자 감소)의 규칙이 반복적으로 이루어지고 있음을 알 수 있다. 이를 좀 더 쉽게 확인하기 위해 분수가 0부터 9까지 변하는 규칙을 그려보면 다음과 같다.

 

 

　an은 지금 반복에서 최대로 늘어나는 분모 혹은 분자의 수(증감 수치)고, bn은 다음 반복에서 최대로 늘어나는 증감 수치다. 이해하기 조금 어려우니 예를 들어보자. 2가 입력되었을 때는 분수가 2/1이다. 이때 다음 반복에서는 증감폭의 최대 수치가 3이므로 an은 2고 bn은 3이다. 3부터 5까지는 분자가 3부터 1까지 줄어들고, 분모가 1부터 3까지 늘어나므로 an은 3이 되고, 6부터는 다시 증감폭이 4로 초기화되므로 5에서의 bn은 4가 되는 것이다.

　이러한 규칙 속에서 an과 bn을 수열로 표현하면 an = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4,...}으로 표현할 수 있고, bn은 {2, 2, 3, 3, 3, 4, 4, 4,...}과 같은 수열로 표현할 수 있다. 이를 기호화하면 다음과 같다.

 

 

　따라서 an을 round(sqrt(2*i))로, bn을 round(sqrt(2 * (i+1))로 정의하였다.

 

		if (an % 2 == 0)
		{
			if (bn > an)
			{
				x = bn;
				y = 1;
				i++;
				continue;
			}

			else
			{
				y--;
				x++;
			}
		}

　이렇게 an과 bn을 정하고 나서, an이 짝수인 경우와 홀수인 경우로 나눠 생각할 수 있다. 먼저 an이 짝수인 경우엔 분자 x가 1부터 an까지 증가하고, 분모 y가 an부터 1까지 감소한다. 그러다 다음 반복의 증감폭이 현재의 증감폭보다 커지면 분모는 1이 되고 분자는 bn이 된다.

 

		else
		{
			if (bn > an)
			{
				y = bn;
				x = 1;
				i++;
				continue;
			}

			else
			{
				x--;
				y++;
			}
		}

		i++;
	}
	cout << x << '/' << y;
}

　반대로 홀수인 경우에는, 분자 x가 an부터 1까지 감소하고, 분모 y가 1부터 an까지 증가한다. 그러다 다음 반복의 증감폭이 현재의 증감폭보다 커지면 분모는 bn이 되고 분자는 1이 된다.

　이러한 연산을 마친 후에 x와 y를 출력해 주면 문제를 해결할 수 있다.

 

총합본

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	int num;
	cin >> num;
	int i = 0;
	int x = 1, y = 1;

	while (i < num)
	{
		int an = round(sqrt(2 * i)); // 현재
		int bn = round(sqrt(2 * (i + 1))); // 다음

		if (an % 2 == 0)
		{
			if (bn > an)
			{
				x = bn;
				y = 1;
				i++;
				continue;
			}

			else
			{
				y--;
				x++;
			}
		}

		else
		{
			if (bn > an)
			{
				y = bn;
				x = 1;
				i++;
				continue;
			}

			else
			{
				x--;
				y++;
			}
		}

		i++;
	}
	cout << x << '/' << y;
}

---

풀이(2) 정수의 위치 추론

　앞선 풀이는 수열의 규칙을 이해하는 과정이 필요해 다소 직관적이지 않은 것 같아, 다른 풀이를 알아보았다. 간단하게 입력된 수의 위치가 어느 위치의 대각선인지를 파악하면 쉽게 해결할 수 있다는 결론을 내렸다.

 

#include <iostream>
using namespace std;

int main() 
{
	int num;
	cin >> num;
	
	int pos = 1; // num의 위치
	while (num > pos) // num의 위치 찾기
	{
		num -= pos;
		pos++;
	}

	if (pos % 2 == 1) // num이 홀수번 째 대각선에 있을 때
		cout << pos + 1 - num << '/' << num;
	else // num이 짝수번 째 대각선에 있을 때
		cout << num << '/' << pos + 1 - num;
}

　pos번 째 대각선에는 pos개의 원소가 있으므로, num이 몇 번째 대각선에, 몇 번째 원소로 있는지 파악하기 위해 pos를 순차적으로 증가시키며 빼주면 된다.

• 따라서 num은 pos번 째 위치에 num번 째 원소가 된다.
• num이 홀수번 째 대각선에 있으면 분자가 증가하고 있으므로 (pos + 1 - num / num)이 된다.
• num이 짝수번 째 대각선에 있으면 분모가 증가하고 있으므로 num / (pos + 1 - num)이 된다.