[BOJ] 1193번 : 분수찾기

🔒 문제

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

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

무	한	히	큰	배	열
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	···	···	···	···	···
···	···	···	···	···	···

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

⌨ 입력

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

🖨 출력

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

📚 예제

Ex1)

1

1/1

Ex2)

2

1/2

EX3)

3

2/1

EX4)

4

3/1

EX5)

5

2/2

EX6)

6

1/3

EX7)

7

1/4

EX8)

8

2/3

EX9)

9

3/2

EX10)

14

2/4

📌 풀이

분수를 a/b로 표현한다면

1. a == 1 일 때
   1) b == 홀수 : b++
   2) b == 짝수 : b가 1이 되기 전까지 a++, b--
2. b == 1 일 때
   1) a == 홀수 : a가 1이 되기 전까지 a--, b++
   2) a == 짝수 : a++

를 하면 된다.

🔑 c언어 코드

#include<stdio.h>

int main() 
{
    int N;
    scanf("%d", &N);
    int a = 1; // 분자
    int b = 1; // 분모
    int n = 1; // 이동 수

    while (1)
    {
        if (n == N)
            break;
        if (a == 1)
        {

            if (b % 2 == 1)
            {
                b++;
                n++;
            }
            else
                while (b != 1)
                {
                    if (n == N)
                        break;
                    b--;
                    a++;
                    n++;
                }
        }
        else if (b == 1)
        {
            if (a % 2 == 1)
                while (a != 1)
                {
                    if (n == N)
                        break;
                    b++;
                    a--;
                    n++;
                }
            else
            {
                a++;
                n++;
            }
        }

    }
    printf("%d/%d", a, b);
    return 0;
}