[C++] 분수 찾기 : 1193번

문제

 

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

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

 

---

문제 해석

지그재그로 진행되는 분수 배열에서 일정한 규칙을 찾아 X번째 분수가 무엇인지 출력하는 문제이다.

개인적인 해석은 이렇다.

분자와 분모를 따로 따로 구해서 접근해야 한다고 생각했고,

각 분자, 분모는 일정한 규칙을 가지고 있다고 생각했다.

또 문제에서 알 수 있는 건, 지그재그로 진행되는 방(층)은 1, 2, 3, 4, 5... 의 형태로 1씩 증가 중이며,

방(층)의 값은 각 방(층)의 분자/분모 중 최대값과 같다.

---

논리 풀이

 

개인적인 생각이므로 가장 최적화된 접근법이 아닐 수도 있음

 

분자 배열

1, 1, 1, 1, 1, ...
2, 2, 2, 2, ...
3, 3, 3, ...
4, 4, ...
5, ...

1     2  3     4  5  6     7  8  9  10   11 12 13 14 15     >> X 번째를 의미
1,    1, 2,    3, 2, 1,    1, 2, 3, 4,     5, 4, 3, 2, 1,          >> 각 X 번째에 해당하는 값
1,       3,         6,             10,                 15,                   >>  X 번째가 있는 방(층)의 최댓값은 해당 층의 모든 값을 더한 값과 같다.

---

분모 배열

1, 2, 3, 4, 5, ...
1, 2, 3, 4, ...
1, 2, 3, ...
1, 2, ...
1, ...

1,    2, 1,    1, 2, 3,    4, 3, 2, 1,    1, 2, 3, 4, 5,

---

이를 통해 유추할 수 있는 점은 해당 층의 원소들을 더한 값은

1,       3,         6,             10,                 15, 

공차가 2, 3, 4, 5 ... 이고 공차가 1인 등차 수열이다.

 

다시 말해, 해당 층의 원소들을 더한 값은 해당 층의 최대 X 번째와 같으므로

 

X 가 속하는 층의 최대값은

1,       3,         6,             10,                 15, 

공차가 2, 3, 4, 5 ... 이고 공차가 1인 등차 수열이다.

 

따라서, 이를 통해 X 는 몇 번째 층에 위치하는지 계산할 수 있다.

이전 문제와 비슷한 원리로써, 이전 문제가 더 간단하므로 아래 링크에서 참고할 수 있다.

 

[C++] 벌집 : 2292번 (tistory.com)

[C++] 벌집 : 2292번

 

X 가 위치한 층수를 알아내게 되면, X의 값도 구할 수 있다.

X 가 만약에 9 라고 가정하면

1     2  3     4  5  6     7  8  9  10   11 12 13 14 15     >> X 번째를 의미
1,    1, 2,    3, 2, 1,    1, 2, 3, 4,     5, 4, 3, 2, 1,          >> 각 X 번째에 해당하는 값

1층    2층    3층            4층                5층

 

9는 4층에 위치한다.

 

여기서 하나의 규칙을 더 발견할 수 있는데,

X층은 최대 X 까지만의 원소를 가진다.

예를 들어, 4층의 경우 4층이 가질 수 있는 원소는 1,2,3,4 가 전부이다.

추가로, 층수가 짝수이면 1, 2, 3, 4 오름차순이고

층수가 홀수이면 5, 4, 3, 2, 1 로 내림차순이 된다.

 

이 규칙에 따라 X 가 속한 층수를 구하고, X 의 층수가 홀수인지 짝수인지에 따라

1 ~ N층 까지 수열을 구하고, 구하는 X의 위치에 따라 X번째 값을 구해낼 수 있다.

 

마찬가지로, 분모에서도 동일한 원리가 적용되며, 분자에 비해 층 수가 짝수인지 홀수인지만 반전된다.

 

코드 풀이

 

#include <iostream>
using namespace std;

int GetNumber(bool isChild, int X);

int main()
{
	int X; // x번째
	cin >> X;
	if (X == 1) // 1일 경우에는 무조건 1/1
	{
		cout << 1 << '/' << 1;
	}
	else
	{
		cout << GetNumber(true, X) << '/' << GetNumber(false, X);
	}
}
int GetNumber(bool isChild, int X)
{
	int child; // 분자
	int parent; // 분모

	int d = 2; // 공차 수열의 초항
	int nowMax = 1; // 현재 시작 위치
	int count = 1; // 방의 위치
	
	while (true)
	{
		nowMax = nowMax + d; // 현재 방의 최댓값
		d += 1; // 공차 1
		count++; // 방 갯수 증가
		if (nowMax >= X) // 현재 방의 최댓값이 찾을 값보다 커지면 찾는 X 번째는 count 번째 방에 있다.
		{
			if (isChild) // 분자를 구할 때
			{
				if (count % 2 == 0) // 현재 방이 짝수라면
				{
					child = count - (nowMax - X); // 현재 방 위치 - (현재방의 최대 번호 - 찾는값) = X 번째가 위치한 방에서의 분자 값
					return child;
				}
				else if (count % 2 != 0) // 현재 방이 홀수라면
				{
					child = 1 + (nowMax - X); // 1 + (현재방의 최대 번호 - 찾는 번호) = X 번째가 위치한 방에서의 분자 값
					return child;
				}
			}
			else // 분모를 구할 때
			{
				if (count % 2 == 0) // 현재 방이 짝수라면
				{
					parent = 1 + (nowMax - X); // 1 + (현재방의 최대 번호 - 찾는 번호) = X 번째가 위치한 방에서의 분자 값
					return parent;
				}
				else if (count % 2 != 0) // 현재 방이 홀수라면
				{
					parent = count - (nowMax - X); // 현재 방 위치 - (현재방의 최대 번호 - 찾는값) = X 번째가 위치한 방에서의 분자 값
					return parent;
				}
			}
		}
	}
}

해당 층에서 X의 값을 구해내는 방법은 다음과 같다.

if (count % 2 == 0) // 현재 방이 짝수라면
{
	child = count - (nowMax - X); // 현재 방 위치 - (현재방의 최대 번호 - 찾는값) = X 번째가 위치한 방에서의 분자 값
	return child;
}
else if (count % 2 != 0) // 현재 방이 홀수라면
{
	child = 1 + (nowMax - X); // 1 + (현재방의 최대 번호 - 찾는 번호) = X 번째가 위치한 방에서의 분자 값
	return child;
}

 

1     2  3     4  5  6     7  8  9  10   11 12 13 14 15     >> X 번째를 의미
1,    1, 2,    3, 2, 1,    1, 2, 3, 4,     5, 4, 3, 2, 1,          >> 각 X 번째에 해당하는 값

 

X 가 9라고 가정할 때, 현재 방(층) 위치 count 는 4 가 된다.

9 가 있는 층의 모든 원소 합은 (nowMax) 1 + 2 + 3 + 4 = 10 이 될 것이고,

현재 층의 최대 번호는 역시 10이 된다.

 

현재 방(층) 위치 - (현재방의 최대 번호 - 찾는값) = 4 - (10 - 9) = 3 이 된다.

 

층이 홀수인 경우에는 1 + (현재방의 최대 번호 - 찾는값) 로 구할 수 있다.