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() {

int n, deno = 1, numer = 1, max = 1, check = 0, cnt = 0; // deno -> 분모값, numer -> 분자값, n -> 입력값, max-> 지그재그의 최댓값, cnt -> 반복문을 조정하기 위한 값

scanf("%d", &n);

if (n != 1) // 입력값이 1이라면 바로 출력하기 위해
{
for (int i = 1; i < n; i++) { // 입력된 수만큼 반복

for (int j = 0; j < max; j++) { // 각 지그재그의 분수 개수는 최댓값임

if (check == max + 1) { // 지그재그의 최댓값만큼 분수 형성시 
max++; // 다음 지그재그
check = 0;
}

cnt++;

if (cnt >= n) // 입력받은 수만큼  연산을 수행하기 위해
break;

if (max % 2 == 1) // 짝수번째 지그재그일 경우
{
if (numer == 1 && deno == max) { // 마지막 홀수번째 분수라면
deno++; // 첫 짝수번째 분수
}

else { // 그 외에
deno--; numer++; // 마지막 짝수번째까지
}
check++;
}

else // 홀수번째 지그재그일 경우
{
if (numer == max && deno == 1) { // 마지막 짝수번째 분수라면
numer++; // 첫 홀수번째 분수
}

else { // 그 외에
numer--; deno++; // 마지막 홀수번째까지
}
check++;
}
}

}
}
printf("%d/%d", numer, deno);
}

★정리★

n번째 분수를 출력하는 프로그램이다.

이 문제의 지그재그 규칙을 이용하여 알고리즘을 설계했다.