백준 1193 - 분수찾기(파이썬)

https://www.acmicpc.net/problem/1193 문제 풀이

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

예제 출력 

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

---

풀이 코드

n= int(input())
index = int((1+((8*n-7)**.5))*.5)
mole= int(n - (index-1)*(index)*.5)
deno = index - mole +1

print(f"{mole}/{deno}" if index %2 ==0 else f"{deno}/{mole}")

코드 해설

먼저 문제 속에 숨어있는 수학적 규칙을 찾아서 풀이했다!!

이해하기 쉽게 배열을 사선으로 나누어 생각해보면 

배열index	분수	전체 인덱스기준 범위
1	1/1	1
2	1/2, 2/1	2~3
3	3/1, 2/2, 1/3	4~6
4	1/4, 2/3, 3/2, 4/1	7~10
5	5/1, 4/2, 3/3, 2/4, 1/5	11~15
6	1/6, 2/5, 3/4, 4/3, 5/2, 6/1	16~21
...	...

이러한 형태가 나오는데 여기서 입력값 n이 몇 번째 index인지 찾고 해당 index에서의 위치를 찾아 출력해주면 된다고 생각했다.

정리를 해보자면

1. 각 배열속 분수의 개수는 index와 동일하게 증가함 = 계차수열

• 입력 n이 몇번째 index인지 구하는 방법 : 
  각 배열의 첫번째 분수의 인덱스는 계차수열(1,2,4,7,11...)이고
  해당 계차수열의 일반항은 이 나온다.  여기서 우리는 An(입력 값)을 알고 있으니 해당 값을 넣어 근의 공식을 이용해 n의 값(index)을 알아내면 된다.
  에 입력값 n을 넣어 나오는 값의 정수부분을 얻으면  우리가 원하는 index값을 얻어낼 수 있다.

2.1) index가 홀수일 경우  :

• 분자는 배열안에서의 위치
  n (입력값)- 이전 index까지의 총개수를 해주면 나옴(index-1까지의 등차수열의 합)
  

  

• 분모는 index+1 - 분자값을 취해주면 됨.

2.2) index가 짝수일 경우 : 홀수일 경우의 역수를 취해주면 간단하게 처리할 수 있다.