[Python]백준_1193 : 분수찾기

Alal11·2022년 11월 3일

boj python

출처

https://www.acmicpc.net/problem/1193

문제

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

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

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

입력

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

출력

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

예제 입출력

알고리즘 분류

수학
구현

➡️문제 분석

대각선이 짝수번째인지 홀수번째인지에 따라 분수의 규칙이 달라진다.

n번째 줄에는 n개의 분수가 있다.
대각선 라인이 짝수이면 분자가 오름차순, 분모가 내림차순이다.
대각선 라인이 홀수이면 분모가 내림차순, 분모가 오름차순이다.

즉, 입력되는 값이 몇 번째 줄의 몇 번째 위치인지 찾고 위에서 찾은 규칙을 적용해준다.

➡️코드(⭕)

n = int(input())                    # 분수 번호 n 입력
line = 1                            # 분수 라인 1부터 시작

while (n > line):                   # n이 line보다 작아질 때까지 반복
    # 입력받은 n을 1씩 늘려가며 빼줌 (몇 번째 줄에 몇 번째 숫자인지 구하기)
    n -= line            # 각 line에서 n이 몇 번째에 위치하는지 알 수 있다.
    line += 1

if line % 2 == 0:                # 대각선이 짝수 라인이라면
    up = n                           # 분자up은 오름차순
    down = line-n+1                  # 분자down은 내림차순
else:                            # 대각선이 홀수 라인이라면
    up = line-n+1                    # 분자up은 내림차순
    down = n                         # 분모down은 오름차순

print(up, down, sep='/')             # 구분자 sep을 이용하여 분수 출력

➡️코드 분석

분수 번호 n을 입력받고, 대각선 line을 1로 선언해준다.
while문으로 n이 몇 번째 줄의 몇 번째에 위치하는지 구한다.

2-1. n이 line보다 작아질 때까지 n에 1씩 늘려가며 빼준다.

2-2. line은 몇 번째 대각선인지, n은 그 대각선에서 몇 번째에 위치하는지를 나타낸다.

2-3. 예를 들어, n=8이면, 2/3 위치이다.
n=8-1=7-2=5-3=2 즉, n=2이고, line=4가 되었을 때 반복문이 멈춘다.
따라서 대각선 4번째 라인의 두 번째에 위치한다는 뜻이다.
if문으로 대각선 line이 짝수일 때와 홀수일 때로 나뉘는데

3-1. line이 짝수이면, 분자는 오름차순(n), 분모는 내림차순(line-n+1)이다.

3-2. line이 홀수이면, 분자는 내림차순(line-n+1), 분모는 오름차순(n)이다.
마지막으로, up과 down을 구분자 '/'로 나눠 출력해준다.