[python] 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번째 분수를 구하는 프로그램을 작성하시오.

해결 방법

1. 몇 번째 라인인지 찾기
2. 라인 내에서 몇 번째인지 찾기
3. 라인이 짝수냐 홀수냐에 따라 규칙을 적용해 출력

이 문제는 지그재그의 규칙을 찾으면 풀 수 있다. 지그재그의 한 라인내 분수의 수는 1, 2, 3, 4로 늘어나며 라인이 짝수 번이면 분자가 1씩 늘어나지만 짝수 번이면 1씩 줄어든다. 숫자를 나열해보면 찾을 수 있음!🙌

while inputN > max: 
    line += 1 
    max += line
gap = max - inputN

gap으로 분모와 분자를 구할 수 있어서 위와같은 과정이 필요하다.

나는 최댓값 자체를 공식으로 구해서 input값과의 차를 이용해 해결하려 했지만 오히려 복잡해지더라...✨ 그래서 아래처럼 했다
챗지피티최고

제출

inputN = int(input()) #입력받기

line = 0 #사선 라인
max = 0 #그 라인에서 마지막 분수가 모든 분수 중 몇번째인지
while inputN > max: #사선 라인 구하기
    line += 1 #line이 1,2,3으로 늘어나면서 최대 번호도 그만큼씩 늘어남
    max += line
gap = max - inputN #라인 내에서 몇번째 분수인지 구하기

if line % 2 == 0: #사선 라인이 짝수번
    top = line - gap 
    under = gap + 1
else:
    top = gap + 1 #사선 라인이 홀수번
    under = line - gap

print(f'{top}/{under}')

메모

레전드 삽질했던 문제지만 이런 규칙 문제가 재밌긴 해 😂♥