BOJ 1193, 분수찾기
ProblemSolving ·이 문제는 구현 혹은 수학문제 입니다.
풀이
분수의 순서를 그려보면
1/1
1/2, 2/1
3/1, 2/2. 1,3
1/4, 2/3, 3/2, 4/1
5/1, 4/2, 3/3, 2/4, 1,5
입니다. 이것을 분자 분모를 따로 생각하면 쉽게 구현하실 수 있습니다.
첫번째 줄에는 1이 최고 숫자이고 두번째 줄에는 2가 최고 숫자, 세번째 줄에는 3가 최고 숫자이고
첫번째 줄에는 분수가 1개 두번째 줄에는 분수가 2개 세번째 줄에는 분수가 3개죠?
그렇다면 n*(n+1)/2 라는 공식으로 줄을 구분할 수 있겠네요!
홀수번째 줄에서는 분자가 최고 숫자부터 1씩 줄어들고 분모는 1부터 시작하고
짝수번째 줄에서는 분자가 1부터 1씩 커지고 분모는 최고숫자부터 1씩 줄어드는 모습을 확인하실 수 있습니다.
이것만 구현하시면 맞출 수 있습니다.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int n, i;
scanf("%d", &n);
for (i = 2; i <= 5000; i++)
if (n <= i*(i + 1) / 2)
break;
n -= (i - 1)*i / 2;
if (i % 2 == 1)
printf("%d/%d", i - (n - 1),n);
else
printf("%d/%d",n , i-(n-1));
return 0;
}