[백준 코딩테스트(Python)] 기본 수학 1 - 분수찾기

1193번: 분수찾기

---

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

 

출력

첫째 줄에 분수를 출력한다.

 

---

1. 문제 접근 방식

이 문제 또한 배열 내 분수들의 규칙성을 찾는 것을 우선적으로 진행해야 한다.

1번째 그룹 : 1/1 (총 1개)
2번째 그룹 : 1/2 2/1 (총 3개)
3번째 그룹 : 3/1 2/2 1/3 (총 6개)
4번째 그룹 : 1/4 2/3 3/2 4/1 (총 10개)
5번째 그룹 : 5/1 4/2 3/3 2/4 1/5 (총 15개)

위의 규칙성을 보면 그룹의 번호만큼 갯수가 추가되는 것을 알 수 있다.

 

분수가 있는 그룹의 번호와 전체 수의 갯수를 구해놓으면 분수를 찾을 때 활용할 수 있다.

이 2개의 수로 gap이라는 순서의 차를 구할 수 있다. (이것 또한 분수를 찾을 때 활용)

# 분수가 위치한 그룹과 그 그룹의 갯수를 구하기
while X > cnt:
    group += 1
    cnt += group
    
# 그룹 마지막 수에서 X번째 분수까지의 순서 차
gap = cnt - X

 

분수들의 나열을 살펴보면 홀수번 그룹은 분자가 1씩 감소하고, 짝수번 그룹은 분모가 1씩 증가한다.

그래서 if절로 조건을 걸어주고 분모와 분자 각각을 설정해준다.

 

그룹이 짝수인 상황을 보면,

분자의 마지막 수는 그룹 번호이고 gap은 마지막 수와 X번째 분수의 순서 차이이므로 그룹 번호에서 gap을 빼준다.

분모의 마지막 수는 늘 1이기 때문에 1에서 gap을 더해준다.

# 그룹이 짝수일 때 (분자가 1씩 커짐)
if group % 2 == 0:
    top = group - gap  
    under = gap + 1 

# 그룹이 홀수일 때 (분자가 1씩 작아짐)
else:
    top = gap + 1  
    under = group - gap

 

2. 풀이 코드

# X는 분수의 위치를 나타냄
X = int(input())

group = 0   # 최대 숫자를 기준으로 만든 그룹의 갯수
cnt = 0     # 전체 수의 갯수

# 분수가 위치한 그룹과 그 그룹의 갯수를 구하기
while X > cnt:
    group += 1
    cnt += group
    
# 그룹 마지막 수에서 X번째 분수까지의 순서 차
# ex. gap = 1 : 마지막 수에서 1만큼 앞에 있는 수
gap = cnt - X

# 그룹이 짝수일 때 (분자가 1씩 커짐)
if group % 2 == 0:
    top = group - gap  
    under = gap + 1

# 그룹이 홀수일 때 (분자가 1씩 작아짐)
else:
    top = gap + 1
    under = group - gap
    
print(f'{top}/{under}')