[백준] 1193번 분수찾기 [Python] - 정수의 합

 

 

 

문제

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

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

출력

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

https://www.acmicpc.net/problem/1463

 

1, 2~3, 4~6, 7~10 ,,, 번째 분수는 각각 분자와 분모의 합이 2, 3, 4, 5, ... 입니다.

분자와 분모의 합이 같은 분수끼리 묶으면

i번째 분수들은 분자와 분모의 합은 i+2입니다.

 

첫 분수부터 i번째 분수들의 총 개수는 $1+2+3+...+i = \frac{i \times (i+1)}{2}$

주어진 정수 n에 대해서 n번째 분수는

$\frac{(i-1) \times i}{2}  < n <= \frac{i \times (i+1)}{2}$을 만족하는 i 번째 분수들에 속해 있습니다.

 

i번째 분수들은

i가 짝수일 때,  분자가 1부터 i까지 증가하고, 분자는 반대로 감소합니다.

i가 홀수 있때는, 분자가 i부터 1까지 감소하고, 분자는 반대로 증가합니다.

 

$d = n - \frac{(i-1) \times i}{2}$ 라고 하면

n번 째 분수는 i 번 째 분수들 중에서 d 번째 분수입니다.

 

>>> i 가 짝수이면, 분자는 d, 분모는 i+1-d

>>> i 가 짝수이면, 분자는 i+1-d, 분모는 d입니다.

 

n=int(input())
i=int((2*n)**0.5)
i+=int(n>(i*(i+1))//2)
d = n - (i*(i-1))//2
if i % 2 == 0:
    print(f"{d}/{i-d+1}")
else:
    print(f"{i-d+1}/{d}")

 

위 코드에서 i를 선택한 방법?

 

$\frac{(i-1) \times i}{2}  < n <= \frac{i \times (i+1)}{2}$
>>> $(i-1) \times i  < 2n <= i \times (i+1)$
>>> $(i-1) \times i  < 2n <= i \times (i+1)$

>>> $(i-1) \times (i-1)  < 2n <= (i+1) \times (i+1)$
>>> $i-1< \sqrt{2n} < i+1$
>>> $\sqrt{2n} - 1 < i < \sqrt{2n} + 1$

>>> $i = [\sqrt{2n}] or [\sqrt{2n}] + 1$

[ ]는 가우스 기호 -> 반올림, 올림, 버림 중에서 버림 -> int$()$ 같은 역할

 

예제 입력 1 

1

예제 출력 1 

1/1

예제 입력 2 

2

예제 출력 2 

1/2

예제 입력 3 

3

예제 출력 3 

2/1

예제 입력 4 

4

예제 출력 4 

3/1

예제 입력 5 복사

5

예제 출력 5 

2/2

예제 입력 6 

6

예제 출력 6 

1/3

예제 입력 7 

7

예제 출력 7 

1/4

예제 입력 8 

8

예제 출력 8 

2/3

예제 입력 9 

9

예제 출력 9 

3/2

예제 입력 10 

14

예제 출력 10 

2/4