1193: 분수찾기

• toc {:toc}

문제

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

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

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

입력

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

출력

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

출처:https://www.acmicpc.net/problem/1193

풀이

(사실 군대 동기의 도움을 받아 아이디어를 얻었다.)

이 문제는 지그재그의 순서로 이동하여 분수를 선택한다.

때문에 / 와 같이 대각선으로 나누어 보면 1번째에 1개, 2번째에 2개, 3번째에 3개로 줄마다 +1씩 늘어난다. 이 부분에서 시그마를 사용해야 한다는 점을 찾았다.

1. 시그마를 사용하여 숫자를 선택해야 하는 줄이 몇 번째 줄인지를 찾아낸다.
2. X-∑m을 통해서 그 줄에 어느 위치에 있는지 찾아낸다.
3. 위치를 찾아낼 때 홀수는 아래에서 위로, 짝수는 위에서 아래로 내려간다는 점을 주의해야 한다.

EX) X=17 이라고 하면 m=5가 된다. 17보다 작은 ∑m은 15이기 때문. 17-15=2로 X가 있는 위치는 6번째 줄의 2번째 위치에 있다는 것을 알 수 있다.

#include <iostream>
 
using namespace std;
 
int main()
{
	int x, m=1, midValue, numerator, denominator;
	cin >> x;
	while((m*m+m)/2<x)
	{
		m++;
	}
	m--;
	midValue = x-((m*m+m)/2);
	if((m+1)%2==0)	// 중간값이 짝수일 때
	{
		numerator = 1;
		denominator = m+1;
		for(int i=1; i<midValue; i++)
		{
			numerator++;
			denominator--;
		}
	}
	else
	{
		numerator = m+1;
		denominator = 1;
		for(int i=1; i<midValue; i++)
		{
			numerator--;
			denominator++;
		}
	}
	
	cout << numerator << "/" << denominator << endl;
		
	return 0;
}

코드가 워낙 중구난방 더러워서 다른 풀이를 참고하면서 간결하게 작성하는 방법을 생각해봐야 할 것 같다.