[BOJ] 1193. 분수 찾기

Python3

문제

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

키워드

• 구현
• 패턴 찾기

문제 풀이

문제 요구사항

• 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 이 차례대로 1번, 2번, 3번, 4번, 5번, … 분수이다.
• X가 주어졌을 때, X번째 분수를 구한다

변수 및 함수 설명

x: 입력받은 x번째의 분수를 구한다
line: 홀수인지 짝수 번째 줄인지를 판단하는 변수이다.
ja: 분자를 나타내는 변수로, /(슬래시) 기준 왼쪽이다.
mo: 분모를 나타내는 변수로, /(슬래시) 기준 오른쪽이다.

로직

• [1], [1/2, 2/1], [3/1, 2/2, 1/3], [1/4, 2/3, 3/2, 4/1].. 이렇게 나타낼 수 있다.
• 홀수 번째인지 짝수 번째 줄인지 판단하고
  - 홀수 줄인 경우에는 분자를 내림차순, 분모를 오름차순으로 정렬한다.
  • 짝수 줄인 경우는 분자를 오름차순, 분모를 내림차순으로 정렬한다.
• x가 line보다 클 때까지 반복한다
  - x에 line만큼 뺀 결과값을 넣고, line을 1 증가시킨다
  • 만약 짝수 번째 줄이라면,
    1) 분자에 x를 넣고
    2) 분모에 line-x+1한 값을 넣는다
  • 만약 홀수 번째 줄이라면,
    1) 분자에 line-x+1을 넣고,
    2) 분모에 x를 넣는다

최종 코드

x = int(input())

line = 0
end = 0

while x > end:
    line += 1
    end += line
    gap = end - x

    if line % 2 == 0:
        ja = line - gap
        mo = gap + 1
    else :
        ja = gap + 1
        mo = line - gap

print(ja, '/', mo, sep='')