백준 1193, 분수찾기

#include <stdio.h>
 
int main(void){
int a, b, X;
 
scanf("%d", &X);
if(X == 1){
    printf("1/1\n");
}
a = 0 ;
do{
    a++;
    b = X-(a*(a+1))/2;
}while(b==0 || b>a+1);
 
if(a%2){
    printf("%d/%d\n",b,(a-b+2));
}else {
    printf("%d/%d\n",(a-b+2),b);
}
 
return 0;
}

대각선 순서대로 1개 2개 3개 4개 5개 . . 의 분수를 갖게 됨

1	2	3	4	5
2	3	4	5
3	4	5
4	5
5

임의의 숫자 X가 a+1번째 대각선에 위의 숫자라면

X = a(a+1)/2 +b

로 표현할 수 있다(1~a까지의 합+b).

또한 n번째 대각선의 분수가 c / d 라면 n = c+d-1 의 규칙을 갖고 있다.

1	2	...	a	a+1	...
		b/(a-b+2) 또는 (a-b+2)/b

따라서 위와 같이 a+1번째 대각선 위의 숫자이며 b 번째인 경우 (지그재그 고려 x 항상 위에서부터 내려간다고 가정)

(분모) = a+1+1-b =(a-b+2) 임을 찾을 수 있다.

b 역시 1부터 a+1 사이의 숫자여야한다.

input으로 들어오는 상수 X에 대해서

a(a+1)/2 + b = X 는 수식이 하나이므로 바로 찾는 방법이 없다( 혹시 수식이 있을까? )

그러므로 while 문으로 a값을 하나씩 올려주면서 b의 값이 조건에 맞을 때까지 loop를 돌린 후,

해당 방향이 위에서 내려올 경우, 올라갈 경우 고려해서 a가 홀수, 짝수일 경우 반전해서 출력한다.