백준 1193번, 분수찾기, Python 3 [BOJ]

음 0.5초에 추가 시간이 없네 ㅎ

 

문제

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

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 - 3 - 3 - 4 - 4 - 4 - 5 - 5 - 5 - 5 - 6... 어?? 뭔가 규칙이 보이는거 같아

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 -10 - 11... ??

 

아니네 삼각형처럼 생각하는게 나을듯

2

33

444

5555

66666

...

 

처음엔 그냥 느낌대로

import sys
num = int(sys.stdin.readline())

#몇번째 줄인가?
def f1(a):
    n = 1
    while True:
        if (n-1)*n/2 < a and a <= n*(n+1)/2:
            return n
        n += 1

a = f1(num)
        
#짝수인가 홀수인가
if a%2 == 0: #짝수일 때
    b = num%a
    print("{}/{}".format(b,num+1-b))

else: #홀수일 때
    b = num%a
    print("{}/{}".format(num+1-b,b))
    

 

와우 바로 틀려버리고

 

다시 살짝만 시간초과 고쳐보자

 

정답

import sys
num = int(sys.stdin.readline())

#몇번째 줄인가?
def f1(a):
    n = 1
    while True:
        if (n-1)*n/2 < a and a <= n*(n+1)/2:
            return n
        n += 1

a = f1(num)
b = int(num-((a-1)*a/2))#몇번째인가?
        
#짝수인가 홀수인가
if a%2 == 0: #짝수일 때
    if b == 0:
        b = a
    print("{}/{}".format(b,a+1-b))

else: 
    if b == 0:
        b = a
    print("{}/{}".format(a+1-b,b))