백준알고리즘 1193번 : 분수찾기[파이썬]

2021. 4. 15. 11:48

문제

무한히 큰 배열에 아래 이미지와 같이 분수들이 적혀있다. 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.


입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.


출력

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


해설

1193번 문제는 규칙을 찾으면 쉽게 풀 수 있다. 첫 번째 규칙 : 밑으로 내려오는 화살표는 짝수 위로 올라가는 화살표는 홀수이다.두 번째 규칙 : 짝수는 분자가 늘어나고 분모가 줄어든다. 홀수는 분자가 줄어들고 분모가 늘어난다. 이러한 규칙을 이용하면 입력 X가 주어졌을 때 분모를 찾아 출력할 수 있다.

 

 


코드

입력 숫자 N이 1이면 1/1을 출력한다. 만약 1이 아니라면 반복문을 이용하여 N보다 tmpval가 커질 때 까지 반복한다. 이때 tmp 몇 번째 줄까지 이동했는지를 저장한다. 조건이 만족하면 해당 줄에서  첫 번째 규칙과 두 번째 규칙을 이용하여 a, b를 구하고 출력한다.

N = int(input())
a, b = 0,0
tmp = 1
tmpval = 1
if N == 1 :
   a, b = 1, 1
else:
    while True :
        if (tmpval >= N) :
            s = tmpval - N
            if tmp%2 == 0:
                if s == 0:
                    a , b = tmp , 1
                else:
                    a , b = tmp-s , 1+s
            else :
                if s == 0:
                    a , b = 1 , tmp
                else :
                    a , b = 1+s, tmp-s
            break
        tmp += 1
        tmpval += tmp

print(a,'/',b,sep='')

참고문헌

 

1193번: 분수찾기

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

www.acmicpc.net