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

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

1193번: 분수찾기

---

풀이 코드

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가 짝수일 경우 : 홀수일 경우의 역수를 취해주면 간단하게 처리할 수 있다.