[백준] 1193 분수찾기 (Python 파이썬)

www.acmicpc.net/problem/1193

1193번: 분수찾기

문제 설명

문제에서, 나열된 분수들을 지그재그 순서로 찾아간다고 했는데, 이 재그재그를 설명하는 예시가 부족해 보였다.

그래서 초반에 이 지그재그 규칙을 찾아내느라 시간을 많이 썼던 것 같다.

 

X가 주어지면 X번째 분수를 출력하면 된다. ( 5번째 분수는 2/2 )

---

풀이 과정

위의 그림을 보면 일정한 규칙이 나타남을 알 수 있다.

라인에 있는 분수의 개수는 1라인은 1개, 2라인은 2개, 3라인은 3개, 4라인은 4개...

이런 식으로 늘어감을 알 수 있다.

 

짝수라인은 시작점에서 끝점으로 갈수록 분자가 1씩 늘어가고 분모가 1씩 감소하며

홀수라인은 시작점에서 끝점으로 갈수록 분자가 1씩 줄어들고 분모가 1씩 늘어난다.

 

그래서 내가 구하고자 하는 수가 몇번째 라인에 있는지, 그 중에서 몇 번째 인덱스에 있는지를 알면 된다.

 

여기서 end는 그 라인의 마지막 인덱스를 뜻한다. ( 1, 3, 6, 10 ... )

그래서 내가 구하고자 하는 인덱스까지 도달할동안 line과 end를 규칙에 따라 늘려가면 쉽게 찾을 수 있을 것이다.

n = int(input())

line = 0
end = 0
while n > end:
    line += 1
    end += line

diff = end - n
if line%2 == 0: #짝수 라인 일때
    top = line - diff
    bottom = diff + 1
else:
    top = diff + 1
    bottom = line - diff

print("%d/%d"%(top,bottom))

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !