백준 문제 중 1193번, 구현, ‘분수찾기’

백준 문제 중 1193번

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

문제

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

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

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

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

…

…

…

…

입력

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

출력

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

---

풀이

1. 규칙을 잘 관찰 해보면 대각선으로 역수 관계에 있는 수끼리 나열 된다는걸 알 수있다.

2. 대각선 한 줄 마다 늘어나는 원소의 개수는 1개 2개 3개 4개… 등차수열로 늘어나고 있음을 알 수있다.

3. 대각선 마다 분모의 최댓값이나 분자의 최댓값이 1씩 증가하고 짝수와 홀수의 방향이 번갈아가며 바뀌며 원소 하나를 이동할때 분자나 분모가 +-1로 변함을 알 수있다.

결론

대각선 마다 단계를 나누어 구별하고 입력으로 받는 수에 해당하는 번째의 단계와 해당 단계 마지막 원소를 기준으로 몇번째 떨어져 있는지를 변수에 저장해 이용한뒤 홀수 단계와 짝수 단계를 나누어 출력한다.

num = int(input())

def next_div(num):
    
    # 해당 단계에서 총 원소의 개수의 합을 나타내는 total
    total = 0
    # 단계를 저장하는 변수 i
    i = 1
    while True:
        total = total + i
     
        if num<=total:
            break

        i+=1

    # i 단계의 총 원소의합에서 num이 얼마나 떨어져 있는지
    j = total - num
    
    # i 단계가 짝수일때와 홀수 일때 출력
    if i%2:
       print(f'{1+j}/{i-j}')
    else:
       print(f'{i-j}/{1+j}')

next_div(num)

배운점

• 규칙을 관찰하고 논리적으로 프로그램을 작성하는 방법을 배웠다.