[백준] 1193번 분수찾기

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

출력

---

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

---

풀이)

규칙을 찾으면 되는 문제이다.

분수를 차례대로 읽는 방법은 지그재그로서 아래 그림처럼 읽는다.

위 그림을 토대로 규칙을 생각해보자.

    포함 숫자                  개수               총 누적 합  

1번째 대각선 :     1                            1                    1

2번째 대각선 :     2,3                          2                    1+2=3

3번째 대각선 :     4,5,6                        3                    3+3=6

4번째 대각선 :     7,8,9,10                    4                    6+4=10

5번째 대각선 :     11,12,13,14,15            5                    10+5=15

N번째 대각선보다 N+1번째 대각선이 숫자를 1개씩 더 포함한다.

그렇다면 우리가 찾을 X가 몇번째 대각선에 속하는지 계산을 통해 알 수 있다.

예시에서 준 것처럼 X가 14라고 하면 X는 

1->3->6->10->15

15보다는 작으니깐 5번째 대각선에 속함을 알 수 있다.

그 다음 분수를 구하는 규칙은 아래와 같다. (대각선이 짝수 대각선인지 홀수 대각선인지가 중요)

X = 14일때 5번째 대각선에 속하는데 

5번째 대각선은 숫자를

11, 12, 13, 14, 15를 포함하고 있다.

14는 앞의 11부터 세었을 때 4번째에 위치하고, 뒤의 15부터 세었을 때 2번째에 위치한다.

앞에서부터 센 수를 분모라고 하고, 뒤에서부터 센 수를 분자라 한다.

이를 이용해 분수로 만들어 보면 2/4이다.

주의할 점은 대각선의 번호가 홀수일때는 앞에서부터 센 수가 분모에 속하나, 번호가 짝수이면 분자가 된다는 것이다.

예를 들어 X = 9일때 4번째 대각선에 속하는데

4번째 대각선은 숫자를

7, 8, 9, 10 을 포함하고 있다.

9는 앞의 7부터 세었을 때 3번째에 위치하고, 뒤의 10부터 세었을 때 2번째에 위치한다.

분수는 3/2이다. 

앞에서부터 센 수가 분자가 됨을 확인할 수 있다.

이를 이용해서 코드를 작성하면된다. 과정을 이러하다.

1. X가 몇번째 대각선에 속하는지 찾기

2. 대각선 숫자 내에서 X가 앞에서부터 몇번째, 뒤에서부터 몇번째인지 찾기

3. 대각선이 홀수인지 짝수인지 확인해서 분수 만들기

설명이 난잡하나, 

몇개의 예시로 직접 계산해보면 어떤 규칙인지 발견하기 쉬울 것이다.

코드)

#include <stdio.h>
using namespace std;
 
int main() {
    int X;
    scanf("%d", &X);
    int start = 0, end = 0; // 대각선에 속하는 첫번째 수와 마지막 수
    int temp = 0; // 몇번째 대각선에 속하는지
    while (end < X) {
        temp++;
        end += temp;
    }
    start = end - temp + 1;
    int a=1; //앞에서부터 세는 수
    int b=1; //뒤에서부터 세는 수
    for (start; start <= end; start++) {
        if (start == X) break;
        a++;
    }
    for (end; end >= start; end--) {
        if (end == X) break;
        b++;
    }
    if(temp % 2 == 0)printf("%d/%d", a, b);//대각선이 짝수번째일때
    else printf("%d/%d", b, a);//대각선이 홀수번째일때
 
    return 0;
}