문제

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

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

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

입력

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

출력

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

예제 입력/출력

코드1

#include <iostream>

using namespace std;

int main() {

	int n, line_num = 1, numerator =1, denominator = 1; // numerator: 분자, denominator: 분모
	bool ck_num1 = false; // 분자가 1부터 시작했는지 여부

	scanf("%d", &n);
	
	for (int i = 1; i != n; i++) {

        // 다른 줄로 넘어갈 때
		if ((ck_num1 == true && denominator == 1) || (ck_num1 == false && numerator == 1)) {
			line_num++;
			
			ck_num1 = !ck_num1;

			if (!ck_num1) {
				numerator = line_num;
				denominator = 1;
			}
			else {
				numerator = 1;
				denominator = line_num;
			}
			continue;
		}

		if (ck_num1) {
			numerator++;
			denominator--;
		}
		else {
			numerator--;
			denominator++;
		}
		
	}

	printf("%d/%d\n", numerator, denominator);

	return 0;
}

풀이1

위 문제의 규칙은 다음과 같이 이루어진다.

첫 번째로 한 생각은 n번이 될때까지 쭉 분수 값을 구하는 것이었다. 하나하나 모든 분수 값을 구하다 보니 생각보다 많은 변수가 필요했다.
대각선을 하나의 라인으로 기준삼아 보면 메인 값이 1,2,3 .. 하나씩 늘어나는 것이 보인다. 그리고 각 대각선의 (분자/분모를 중심으로) 증감이 변한다는 것을 발견할 수 있다. 이에 대한 모든 분수를 구하는 것을 코드로 적용 시키다보니 더 힘들어 졌다.

코드2

#include <iostream>

using namespace std;

int main() {

	int line_num, n, sum = 0;

	scanf("%d", &n);

    // n번째 대각선까지 가질 수 있는 분수의 최대 개수
	for (line_num = 1; sum < n; line_num++)
		sum += line_num;

	line_num--; // for문 증감문을 통해 원하는 대각선보다 하나 더 더해졌으므로 -1함.

	if (line_num % 2) // 홀수
		printf("%d/%d\n", sum - n + 1, line_num - sum + n);
	else // 짝수
		printf("%d/%d\n", line_num - sum + n, sum - n + 1);

	return 0;
}

풀이2

‘코드1’ 보다 좀 더 간결한 코드를 짜는 방안을 생각했다. 규칙을 되짚어보자면

1. 대각선(1사분면->3사분면의 방향)을 중심으로 분자 혹은 분모의 시작 숫자가 1,2,3 … 1씩 증가.
2. 대각선의 시작점에서 끝점까지 분자 혹은 분모는 1씩 감소/증가를 보임.
3. 대각선을 중심으로 n번째 대각선 라인의 총 분수 개수는 1, 3, 6, 10, 15 .. 의 형태로 증가하며 이것은 +2 -> +3 -> +4 .. 규칙적인 증가 값을 갖음.

위와 같은 규칙을 갖고 있는 것을 알 수 있다.
특히 2번을 자세하게 보면 대각선의 분자/분모의 시작숫자(코드상 line_num)가 ‘짝수’일때는 분자는 +1씩 증가하고, 분모는 -1씩 감소한다. 반면에 시작숫자(코드상 line_num)가 ‘홀수’일때는 반대로 분자는 -1씩, 분모는 +1씩 바뀌는 것을 볼 수 있다.
line_num = 4 를 예로 들자면, 1/4 -> 2/3 -> 3/2 -> 4/1 , 에서 보이듯이 시작숫자가 짝수고 분자는 +1씩, 분모는 -1씩 바뀌는 것을 볼 수 있다.
이를 참고해서 구현하면 위의 ‘코드2’와 같이 구현된다.