날짜: 2021년 5월 21일
소요 시간: 26분 18초
카테고리: 수학 문제
태그: Bronze.2, 1193, 파이썬

백준 1193 - 분수찾기

입출력 예시

내가 적은 코드

X = int(input())
k = X
count = 1
i = 1
while (k > count):
    k -= count
    count += 1
if count%2 == 1:
    a = count + 1 - k
    b = k
else:
    a = k
    b = count + 1 - k
print (a,b, sep='/')

풀이 과정

그림의 빨간색 화살표와 같은 순서로 순차적으로 진행되었을 때 X번째 분수를 구하기 위해서 단락을 나누어 count로 저장하였다.
(처음 X를 저장한 k는 단락이 넘어갈 때 마다 count만큼 차감된다.)
(ex. 14 -> 13 -> 11 -> 8 -> 4)

파란색 박스를 기준으로 잡았을 때
1/1 -> 1/2, 2/1 -> 3/1, 2/2, 1/3 -> …
순서로 출력 된다.

이런식으로 진행되었을 때 몇번째 count의 몇번째 수를 찾아낼 수 있다.
(ex. 14번째 수 -> 5번째 단락의 4번째 수)

그림의 화살표와 파란색 박스를 살펴보면
count가 짝수이면 분모(a)가 n부터 1까지 줄어들고, 분자(b)는 1부터 n까지 증가한다.
count가 홀수이면 분자(b)는 1부터 n까지 증가하고, 분모(a)가 n부터 1까지 줄어든다.

규칙만 찾아 낸다면 그렇게 어렵지 않은 문제 였다.

베스트 코드

n = int(input())
c = 2
m = 1

while True:
  if m < n:
    m += c
    c += 1
  else :
    if (c % 2) == 0:
      print(str(1+(m-n))+"/"+str((c-1) - (m-n)))
      break
    else:
      print(str((c-1) - (m-n))+"/"+str(1+(m-n)))
      break

반성

• 그냥 print했다가 분자,/,분모 사이에 공백이 생긴다는 점을 인지하지 못해서 시간을 많이 버렸다.