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

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

1193번: 분수찾기

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 수학
 - 구현

문제

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

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

출력

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

 

---

최대 수가 10,000,000 이기 때문에 배열에 하나하나 할당해서 풀 순 없고

 

규칙성을 찾아야 한다.

 

1	2	6	7	15	…
3	5	8	14	…	…
4	9	13	…	…	…
10	12	…	…	…	…
11	…	…	…	…	…
…	…	…	…	…	…

위와 같은 순서이며

 

방향을 바꿔 생각하면 맨 위열을

 

1 2 4 7 11...

의 규칙성을 찾을 수 있다.

 

이는 계차수열로

 

1 2 4 7 11 16

 1 2 3  4   5

 

위와 같은 규칙을 찾을 수 있으며

 

등차수열의 일반 해를 찾는 방법은

 

$  a_{n} = a_{1} + (n-1)d $

 

$ a_{n} = 1 + (n-1) $ 

$ a_{n} = n $ 으로 표기할 수 있다.

 

그리고 위 1 2 4 7 11 16... 의 규칙에서 다음 수를 찾는 방법은

 

첫째항 1과 그다음 위에서 찾은 등차수열 $ a_{n} $의 합

 

$ a_{1} + ... + a_{n} =  \frac{\mathrm{n(n-1)}}{2} $ 에 첫째항 1을 더해주면 찾고자 하는 위치의 값을 알 수 있다.

 

즉

$$ 1 +  \frac{\mathrm{n(n-1)}}{2}$$ 이 찾는 방식이다.

 

그다음 각 순서의 홀수번째와 짝수번째를 구분하여 분모와 분자를 찾아주면 끝

 

import sys
import math
input = sys.stdin.readline

n = int(input())
i = 1
now = 1
while True:
    now = 1 + (i*(i-1))//2
    next = 1 + ((i+1)*i)//2
    if now <= n and n < next:
        break
    if next > 10000000:
        break
    i += 1

if i % 2 == 0:
    gap = n - now
    row = 1 + gap
    col = i - gap
else:
    gap = n - now
    col = 1 + gap
    row = i - gap
print(row, col, sep="/")