[백준/C언어] 1193번: 분수 찾기

 

문제

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

 

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

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

 

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

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

 

---

 

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {

	int input;
	int s = 1;
	int i, j, k;

	scanf("%d", &input);

	while (1) {
		if (input <= s * (s + 1) / 2) {
			break;
		}
		s++;
	}

	i = (s - 1) * s / 2;
	j = input - i;
	k = s - j + 1;

	if (s % 2 == 0) {
		printf("%d/%d\n", j, k);
	}
	else {
		printf("%d/%d\n", k, j);
	}

	return 0;
}

 

 

 

---

 

배열표를 돌려서 보면 위쪽이 삼각형의 형태를 가지고 있다는 것을 알 수 있다. 각 줄의 패턴을 확인해보면, 분수들은 2번째 줄에 2개, 3번째 줄에 3개, ..., s번째 줄에는 s개의 분수를 가지므로 총 s * (s + 1) / 2 개의 분수를 가진다.

 

입력받은 input이 속해 있는 줄이 s라고 할 때, input은 1부터 s-1까지의 합보다 크고, s까지의 합보다는 작다.

j를 분자, k를 분모라고 할 때, s를 위에서 구했으므로 s-1번째 줄 까지의 개수를 i =  (s - 1) * s / 2 로 구할 수 있다. 또한 짝수를 기준으로 분자 j는 input - i로 구할 수 있으며, 모든 분수에서 s = j + k + 1이 성립하므로 분모 k는 s - j + 1을 통해 구할 수 있다.

홀수의 경우에는 분모와 분자의 위치를 바꿔주면 되기 때문에 if~else문을 사용하여 원하는 순서의 분수를 찾아 출력할 수 있다.