[BOJ] 1193. 분수 찾기 (C)

• 코딩 초보

---

1193. 분수 찾기

 

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

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

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

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

 

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

 

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

 

---

규칙을 찾아서 해결하는 문제이다. 

 

처음에 문제를 잘못 이해하고 풀어서 조금 헤맸었다. 지그재그 순서로 분수의 분자와 분모가 어떻게 변화하는지를 관찰하고 규칙을 찾아내면 된다. 

 

 

#include <stdio.h>

main() {
	int x,a,b,line=1,sum,temp=0;
	scanf("%d", &x); 

	while (1) {
		sum = (line) * (line + 1) / 2; 
		if (temp < x && x <= sum) break; 
		line++; 
		temp = sum; 
	}

	if (line % 2 == 0) {
		a = 1; b = line;

		if (x == temp + 1) {
			printf("%d/%d", a, b); 
		}
		else {
			for (int i = temp+1; i < x; i++) {
				a++;
				b--;
			}
			printf("%d/%d", a, b); 
		}
	}
	else {
		a = line; b = 1; 

		if (x == temp + 1) {
			printf("%d/%d", a, b);
		}
		else {
			for (int i = temp + 1; i < x; i++) {
				a--;
				b++;
			}
			printf("%d/%d", a, b); 
		}
	}
}

 

홀수번째 라인의 경우, 분모가 1, 분자가 라인의 수로 시작하며 순서가 증가할수록 분자는 감소하고 분모는 증가하고 있으며, 짝수번째 라인의 경우는 반대로 분자는 증가하고 분모는 감소하고 있다. 

 

입력한 X가 몇번째 라인인지를 파악하기 위해서 등차수열의 합을 이용하였다. 

1번째 라인에는 1

2번째 라인은 1+2 = 3 

3번째 라인은 1+2+3 = 6 개의 값들이 있으므로 

 

만약 5번째가 몇번째 라인에 있는지를 파악하고 싶을때에는 

그 전의 라인에 있는 값들의 개수 (2번째 라인, 3) 과 현재 라인에 있는 값들의 개수 (3번쨰 라인, 6) 그 사이에 있는 수이면 된다. 따라서 5번째 수가 3번째 라인에 있는 수임을 파악할 수 있다. 

 

그렇게 몇번째 라인임을 구하고, 그 라인이 홀수인지 짝수인지를 파악하는 if 조건문을 짜주었다. 

 

먼저 짝수번째 라인의 경우 x가 temp(그 이전 라인에 저장된 값들의 개수)보다 1 큰 것과 같은 경우는 라인의 시작 시점이므로 그냥 라인의 첫번째 값을 그대로 출력하도록 하였다.

만약 라인의 첫번째 시작 분수가 아니라면, temp보다 1 큰수에서 시작하므로 temp가 x보다 작을때까지 분자를 증가시키고 분모를 감소시켜서 반복문을 돌게 한 다음, 최종적으로 printf 하도록 하였다. 

 

홀수 번째 라인도 같은 방식으로 코드를 짜주었다.

 

예를 들어 5번째 분수를 출력한다고 하자. 앞서서 5번째 분수는 3번째 라인에 있고, 그 전 라인은 2번째 라인(2번째 라인까지 총3번째 분수가 있음을 기억. temp 는 3) 임을 알고 있다. 3번째 라인은 홀수번째 라인이므로 else 조건문으로 이동한다. 

분자는 3, 분모는 1로 초기 설정을 마친다. 

 

temp+1은 4이고 x는 5이므로, 서로 같지 않아서 라인의 첫번째 수가 아님을 알고 else 조건문으로 이동해서 동작을 수행한다. 

i가 4일때 분자는 2 분모는 2 

i가 5일때는 x보다 작지 않으므로 수행하지 않는다.

따라서 분자와 분모에는 각각 2 가 저장되어 있으므로

출력도 2/2 로 출력된다.