[백준]1193번: 분수찾기

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

1193번: 분수찾기

---

분수들을 위와 같은 지그재그 순서로 읽는다고 함

 

분자랑 분모랑 따로 생각해보면 각각 아래와 같은 수열을 이룬다

분자 : ( 1 ) ( 1 2 ) ( 3 2 1 ) ( 1 2 3 4 ) ( 5 4 3 2 1 ) ( 1 2 3 4 5 6 ) ...

분모 : ( 1 ) ( 2 1 ) ( 1 2 3 ) ( 4 3 2 1 ) ( 1 2 3 4 5 ) ( 6 5 4 3 2 1 ) ...

 

저렇게 나열하고 나니까 군수열이라는 생각이 들었다.

그래서 예전에 작성해둔, 군수열의 n번째 항의 값을 출력하는 코드를 살짝만 수정해서 제출하였다.

 

(군수열 간단한 개념과 python코드 보러가기)

 

python 정답 코드

x = int(input())
 
flag = True
n = 1
nCnt = 1
den, num = 0, 0 # 분모, 분자
while flag:
  for i in range(1,n+1):
    nCnt += 1
    if nCnt > x:
      if n%2 == 0:
        den = i
        num = n-i+1
      else:
        den = n-i+1
        num = i
      flag = False
      break
  n += 1
  

print('{}/{}'.format(den,num))

python3로 제출하면 시간초과가 나고, pypy3로 제출해야 정답 판정을 받았다.