백준(BOJ) - 분수찾기(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)가 주어진다.

출력

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

 

분수를 보면 분자,분모가 2차원 배열의 인덱스 값(1부터 시작하는)과 같다는건 쉽게 보인다.

 

다음으로 

이렇게 대각선을 기준으로 보면 처음1/1을 1줄이라하면 각 줄의 시작값(가장 작은값은)

1줄 : 1

2줄 : 2

3줄 : 4

4줄 : 7

5줄 :11

..

이러한 규칙이 있고 각 줄이 증가값이 1,2,3,4,5.. 이다. 이것을 일반식 코드로 표현하면 

  Value += k++ 라 볼수 있다. (k줄의 값은 Value)   점화식: ( f(n) = f(n-1) + n-1 (n>=2),  f(1)=1)

 

n값이 몇 번째 줄인지 알고, 그 줄에서 몇번째 수인지를 알면 인덱스 값을 알아낼수있다.

 

짝수 줄은 왼쪽 대각선 아래로 증가하고 홀수 줄은 오른쪽 대각선 위로 증가하는 것만 조심하자.

 

import sys
sys.setrecursionlimit(100000000)
input=sys.stdin.readline

def fun(n):
    if n==1:
        return 1
    else:
        # n줄의 값 f(n)=f(n-1)+(n-1)이다
        return fun(n-1)+n-1

x=int(input().rstrip())

for i in range(1,x+1):

    if fun(i)<=x<fun(i+1):
        
        # x는 tmp줄에 있는 숫자이고 tmp줄의 첫번째 값은 val
        tmp=i
        val=fun(i)
        break
    
if tmp%2==0:
    # 짝수번 줄은 값이 증가할수록 y인덱스가 감소하므로 빼기
    y=tmp-(x-val)
    # x인덱스는 반대로 커짐.
    x=1+(x-val)
# 홀수번 줄은 짝수와 x,y인덱스 각각 반대임
else:
    y=1+(x-val)
    x=tmp-(x-val)

print(x,"/",y,sep='')

 

x가 10,000,000까지의 수라서 시간초과가 난다. 불필요한 코드를 간단하게 해주자

 

import sys
sys.setrecursionlimit(100000000)
input=sys.stdin.readline


x=int(input().rstrip())

i=1
res=1
while x>=res:
    tmp=res
    tmp_i=i
    res+=i
    i+=1
i=tmp_i
res=tmp

if i%2==0:
    # 짝수번 줄은 값이 증가할수록 y인덱스가 감소하므로 빼기
    y=i-(x-res)
    # x인덱스는 반대로 커짐.
    x=1+(x-res)
# 홀수번 줄은 짝수와 x,y인덱스 각각 반대임
else:
    y=1+(x-res)
    x=i-(x-res)

print(x,"/",y,sep='')