백준(BAEKJOON): 분수찾기(1193번)

Source

문제

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

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

출력

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

예제 입력 1

14

예제 출력 1

2/4

해설

솔직히 코딩보다 규칙을 찾는 데 훨씬 애를 먹었다. 학교 다닐 때 수학을 제대로 공부할걸 하는 후회를 했다. 하지만 수학 문제를 풀이를 열심히 했다고 이 문제의 규칙을 금방 찾아냈을까 하는 의구심을 떨칠 수 없다. 뭐가 됐든 규칙을 찾아내는데 10이 들었다면 코딩은 0.1이었다. 이 문제에서 고비를 맞았던 모든 이들에게 위로를 드리며 코딩 자체보다 규칙과 공식을 찾는 데 시간을 투자하시길.

우선 제시된 문제를 좀 더 간단하게 도식화해 보자.

1: 1/1
2: 1/2 2/1
3: 3/1 2/2 1/3
4: 4/1 3/2 2/3 1/4
5: 1/5 2/4 3/3 4/2 5/1
6: 6/1 5/2 4/3 3/4 2/5 1/6
...

입력된 x번째 분수의 위치를 찾기 위해서는 이 분수이 위치하는 라인을 알아내야 한다. 14번째 분수는 5번 라인에 있다. 어떻게 알 수 있을까?

분수의 개수는 1라인에 1개, 2라인에 2개, 3라인의 3개 ... N라인 N개가 된다. 측 N라인까지의 분수의 총 개수를 계산하여 이 수가 입력된 x번째를 포함하고 있는지 알아내야 한다. 먼저 N라인까지 분수의 총 개수는 가우스 공식(명칭이 맞나 모르겠다.)을 이용할 수 있다.
가우스 공식이란 1 ~ n까지의 수의 합계를 구하는 공식이다. 예를 들어 10까지의 합계는 55인데 1 + 2 ... 으로 차근차근 계산할 수 있지만 아래와 같이 풀 수도 있다.

1 2 3 4 5 6 7 8 9 10

• 10 9 8 7 6 5 4 3 2 1
  11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 => 110

1부터 10까지의 수가 두 세트가 있다고 가정하자. 위와 같이 바른 순서와 역순으로 배열하여 각각을 합하면 11이 총 10개 나온다. 이 모두를 합하면(11 * 10) 110이 된다. 우리가 원래 구하고 싶었던 것은 110까지 1벌의 합이라는 걸 잊지 말자. 우리가 방금 구한 합은 110까지 2벌의 합이므로 우리가 구한 합을 2로 나누어 주어야 한다. 110 / 2 하면 55가 된다.
이 방식으로 x번째 분수가 들어있는 라인을 확인하는 코드를 아래와 같이 작성한다.

    int line = 0;
    scanf("%d", &input_num);
    while (line    * (line + 1) / 2 < input_num) {
        line++;
    }

즉 14번째 분수는 조건식 5 * (5 + 1) / 2 < 14을 통과하지 못하여 변수 line = 5로 while문이 종료된다.

x번째 분수가 포함된 라인 번호 line을 알아냈으므로 이 직적 라인 (line - 1)까지의 분수의 총 개수에서 x번째를 빼면 아래 코드에서와 같이 해당 line에서 몇 번째 분수인지 알 수 있다.

    rest = input_num - (line - 1) * ((line - 1) + 1) / 2;

이제는 분수의 분모, 분자의 변화를 눈여겨 보자. 홀수와 짝수 라인의 분모, 분자값의 변화가 상이하다. 라인 번호가 짝수일 때는 분자가 라인 번호에서 시작하여 1까지 1씩 줄어들며, 분자는 1부터 라인 번호까지 증가한다. 한편 라인 번호가 홀수일 때는 반대의 상황인 것이다. 따라서 라인 번호가 짝수인지 홀수인지에 따라 처리를 달리해야 한다. 앞서 알아낸 rest값과 라인의 짝홀에 따른 분자 분모의 변화를 고려하여 출력 코드를 아래와 같이 완성하였다.

    if (line % 2 == 0) {
        printf("%d/%d\n", rest, line - (rest - 1));
    } else {
        printf("%d/%d\n", line - (rest - 1), rest);
    }

지금까지의 코드를 완성하면 아래와 같다.

소스코드

#include <stdio.h>
int main(int argc, char *argv[])
{
    int input_num, line = 0, rest;

    scanf("%d", &input_num);
    while (line    * (line + 1) / 2 < input_num) {
        line++;
    }

    rest = input_num - (line - 1) * ((line - 1) + 1) / 2;

    if (line % 2 == 0) {
        printf("%d/%d\n", rest, line - (rest - 1));
    } else {
        printf("%d/%d\n", line - (rest - 1), rest);
    }

    return 0;
}