[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>

int main(void) {
	
	int x;
	int n = 1;
	int cnt = 0;
	int total = 0;
	
	scanf("%d", &x); //숫자 입력 
	
	int temp = x;
	
    //껍질이 쌓일수록 칸의 갯수는 1씩 증가하기 때문에 1부터 빼주면서 몇번째 대각선에 있는지 확인
	while(temp > 0) { //x에서 n을 빼가며 계산하기 위해 임시로 temp를 만들어 음수가 될 때까지 반복
		if(temp - n <= 0) { //다음 번에 음수가 된다면 탈출
			break;
		}
		temp -= n;
		cnt++;
		n++;
	}
 	
    //껍질 수만큼 지나온 분수 개수 
	for(int i = 1; i < cnt + 1; i++) { //껍질은 1씩 증가하며 커지기 때문에 1씩 증가시키며 껍질 수만큼 합산
		total += i;
	}
	
	int pre = x - total; //앞글자는 입력 받은 x에서 지나온 칸 개수를 빼준 값이다
	int post = (cnt + 1) - (pre - 1); //뒷글자는 껍질수 + 1에서 앞글자 - 1을 뺀 값이다

	//껍질이 늘어날 때마다 분모와 분자가 서로 바뀐다
	if((cnt + 1) % 2 == 0) {  //짝수라면 정순
		printf("%d/%d", pre, post); 
	}
	else { //홀수라면 역순
		printf("%d/%d", post, pre); 
	}
	
	return 0;
}