[C] 1193번: 분수찾기

문제#

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)가 주어진다.

출력#

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

풀이#

분수들은 대각선 단위로 묶어서 생각할 수 있습니다.

• 1번째 대각선: 1개
• 2번째 대각선: 2개
• 3번째 대각선: 3개
• …

즉, 현재 번호가 어느 대각선에 속하는지 찾기 위해 1, 2, 3, ...을 차례대로 빼면 됩니다.

예를 들어 X가 어떤 대각선에 들어왔을 때,

• 그 대각선 번호가 홀수이면 위에서 아래 방향
• 짝수이면 아래에서 위 방향

으로 분자가 결정됩니다.

따라서 대각선 번호의 홀짝에 따라 분자와 분모를 다르게 출력하면 됩니다.

코드#

1
#include <stdio.h>
2

3
int main() {
4
    int x;
5
    int line = 1;
6

7
    scanf("%d", &x);
8

9
    while (x > line) {
10
        x -= line;
11
        line++;
12
    }
13

14
    if (line % 2 == 1) {
15
        printf("%d/%d\n", line + 1 - x, x);
16
    } else {
17
        printf("%d/%d\n", x, line + 1 - x);
18
    }
19

20
    return 0;
21
}