[C]백준_1193 : 분수 찾기

Alal11·2023년 1월 7일

C boj

출처

https://www.acmicpc.net/problem/1193

문제

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

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

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

입력

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

출력

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

예제 입출력

알고리즘 분류

수학
구현

➡️문제 분석

대각선이 짝수번째인지 홀수번째인지에 따라 분수의 규칙이 달라진다.

n번째 줄에는 n개의 분수가 있다.

대각선 라인이 짝수이면 분자가 오름차순, 분모가 내림차순이다.
대각선 라인이 홀수이면 분모가 내림차순, 분모가 오름차순이다.

즉, 입력되는 값이 몇 번째 줄의 몇 번째 위치인지 찾고 위에서 찾은 규칙을 적용해준다.

➡️코드(⭕)

#include <stdio.h>

int main()
{
	int n, diff, top, bottom, line = 0, end = 0;
	// line은 대각선으로 그었을 때 짝수 또는 홀수 번째에 있는지 판별하는 변수
	// end는 해당 라인의 가장 끝의 번째(1, 3, 6, 10, ...)를 나타내는 변수


	scanf("%d", &n);				// 몇 번째 분수인지 n으로 입력 받음

	while (n > end) {				// n이 end보다 클 때까지 반복
		line += 1;					// line의 수 1씩 증가
		end += line;				// end에 line 누적합 구해서 라인의 끝의 번째 구함
	}

	diff = end - n;					// diff에 해당 라인의 끝 번째와 실제 입력받은 번째의 차이를 넣음

	if (line % 2 == 0) {			// line이 짝수라면
		top = line - diff;			// 분자 
		bottom = diff + 1;			// 분모
	}
	else {							// line이 홀수라면
		top = diff + 1;				// 분자
		bottom = line - diff;		// 분모
	}

	printf("%d/%d", top, bottom);	// 분자/분모 형식으로 출력
}