[백준 1193번 파이썬] 분수찾기

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

 

입력받은 숫자 번째에 위치한 분수를 출력해주면 되는 문제이다

여기에서 숫자 번째는 이 표와 같이 지그재그로 세는 것으로

첫 번째는 1/1, 두 번째는 1/2, 세 번째는 2/1, 네 번째는 3/1과 같은 형식을 띤다

 

num = int(input())
line = 0
max_num = 0
while num > max_num:
    line += 1
    max_num += line
gap = max_num - num
if line % 2 == 0:
    top = line - gap
    under = gap + 1
else:
    top = gap + 1
    under = line - gap
print(f'{top}/{under}')

 

이 챕터에서는 문제 속에 있는 수식을 찾아내는 게 주된 것으로

이번 문제에서 우리가 찾아야 한 것은 공차가 1인 등차수열로 지그재그 줄을 찾을 수 있고,

홀수와 짝수 줄에 따라 top과 under가 반대로 증가/감소하는 것을 이용할 수 있는 수식이다

위의 정답 코드를 보다 자세히 설명하기 위한 예시로 만약 7번째 분수를 출력받고자 한다면

while을 통해서 max_num은 10, line은 4가 될 거고,

gap에는 10 - 7인 3이 들어간다

현재 line이 짝수이기 때문에 if 문 안으로 들어가 4 - 3을 top에 넣고

under에는 gap인 3에다가 1을 더한 4가 들어가게 된다

즉, 7번째 분수는 1/4가 된다