백준 > 단계별로 풀어보기 > 일반 수학 1 > 1193번: 분수찾기

문제

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

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

이와 같이 나열된 분수들을 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 복사

2

예제 출력 2 복사

1/2

예제 입력 3 복사

3

예제 출력 3 복사

2/1

예제 입력 4 복사

4

예제 출력 4 복사

3/1

예제 입력 5 복사

5

예제 출력 5 복사

2/2

예제 입력 6 복사

6

예제 출력 6 복사

1/3

예제 입력 7 복사

7

예제 출력 7 복사

1/4

예제 입력 8 복사

8

예제 출력 8 복사

2/3

예제 입력 9 복사

9

예제 출력 9 복사

3/2

예제 입력 10 복사

14

예제 출력 10 복사

2/4

 

X = int(input())

line = 0
end_of_line = 0

while X > end_of_line:
    line += 1
    end_of_line += line

gap = end_of_line - X

if line % 2 == 0:
    boonja = line - gap
    boonmo = gap + 1

if line % 2 == 1:
    boonja = gap + 1
    boonmo = line - gap

print(f"{boonja}/{boonmo}")

 

분수 순서

1/1 -> 1/2, 2/1 -> 3/1, 2/2, 1/3 -> 1/4, 2/3, 3/2, 4/1 순

첫 번째 대각선 1/1

두 번째 대각선 1/2, 2/1

세 번째 대각선 3/1, 2/2, 1/3

네 번째 대각선 1/4, 2/3, 3/2, 4/1

 

주어진 수가 7일 때 답은 1/4임. 1/4는 7번째 분수이며 네 번째 대각선에 존재함.

또한 첫 번째 대각선은 하나의 분수

두 번째 대각선은 두 개의 분수

세 번째 대각선은 세 개의 분수

네 번째 대각선은 네 개의 분수를 가짐

end_of_line을 구하는 이유는 몇 번째 대각선에 위치하는지를 알기 위해서임

즉 네 번째 대각선의 경우 end_of_line은 10이 됨

실제로 네 번째 대각선까지 분수들의 개수의 합은 10임

 

end_of_line은 각 대각선의 끝 번호를 나타냄

예를 들어, 1번째 대각선의 끝 번호는 1, 2번째 대각선의 끝 번호는 3(1+2), 3번째 대각선의 끝 번호는 6(1+2+3), 4번째 대각선의 끝 번호는 10(1+2+3+4)임

 

X가 end_of_line보다 작거나 같아지는 시점에서, 해당 X는 그 대각선에 속하게 됨 

 

gap은 해당 대각선의 끝 번호에서 X를 뺀 값으로, 대각선의 끝에서 X가 몇 번째 위치에 있는지를 보여줌

 

X=7일 경우 end_of_line은 10이며 gap은 3으로 X 번째 수는 end_of_line(대각선의 끝 번호)로부터 3번째 위치에 있음

 

짝수번째 대각선의 경우

분자는 1부터 1씩 커지고

분모는 대각선의 번호부터 1씩 감소함

 

홀수번째 대각선의 경우

분자는 대각선의 번호부터 1씩 감소하고

분모는 1부터 1씩 커짐 

 

아직도 잘 모르겠다..