[C] 백준알고리즘 #1193 분수찾기

백준알고리즘 #1193 분수찾기 문제

X가 주어졌을 때 X번째 분수를 구하는 문제이다.

규칙을 잘 살펴보면

규칙

위와 같은 순서대로 X의 번호가 진행됨을 알 수 있다.

각 대각선에 있는 수의 개수는 1,2,3...순으로 늘어나기 때문에

1부터 n까지 더했을 때 X보다 크지 않으면서 가장 가까운 수를 구한다.

이를 위해서 X가 0보다 작아질 때까지 1,2,3.. 순으로 뺄셈해준다.

int ln = 0;
while (n > 0) {
	ln++;
	n -= ln;
}

이 결과의 ln변수는 x가 몇번째 대각선에 있는지 알려준다.

그리고 남아 있는 x는 음수 또는 0이 될 것이므로 다시 ln을 한번 더해주면 (ln)번째 줄의 몇번째 위치에 있는지 알 수 있다. 이를 count 변수에 저장해둔다. 

 

이 ln 변수에 저장된 값이 짝수라면 위에서부터 왼쪽 아래로 내려올 것이고

홀수라면 아래에서부터 오른쪽 위로 올라갈 것이다.

 

때문에 짝수일 때는 분자가 1부터 count만큼 증가하고 홀수일 때는 분모가 1부터 count만큼 증가한다.

반대로 짝수일 때의 분모와 홀수일 때의 분자는 ln(줄 번호) - count + 1 ( count와 ln이 같은 경우 0이되버리기때문) 이 된다.

 

#include <stdio.h>
int main() {
	int n;
	int ln = 0;
	int count;
	int mom, son;
	scanf_s("%d", &n);
	while (n > 0) {
		ln++;
		n -= ln;
	}
	count = n + ln; // ln줄에서 시작하고 남은 수
	

	if (ln % 2 == 0) {
		mom = ln - count + 1;
		son = count;
	}
	else {
		mom = count;
		son = ln - count + 1;
	}

	printf("%d/%d", son, mom);
}