백준 1193번 파이썬 풀이: 분수찾기

백준 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/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 이런식으로 진행이 된다.

 

아직 감이 오지않는 사람들을 위해 조금더 구분을 해주자면

 

1/1 ->      1/2 -> 2/1 ->      3/1 -> 2/2 -> 1/3

 

1개 2개 3개 이런식으로 n개씩 늘어난다고 친다면

 

홀수씩 늘어날 때는 분자는 n부터 1까지 줄어들고 분모는 1부터 n까지 늘어난다.

짝수씩 늘어날 때는 분자는 1부터 n까지 늘어나고 분모는 n부터 1까지 줄어든다.

 

이 규칙을 발견하기까지가 쉽지 않은 문제였다.

 

 

코드

# 1193번

x = int(input())
num_list = []

num = 0
num_count = 0

while num_count < x:
    num += 1
    num_count += num

num_count -= num

if num % 2 == 0:
    i = x - num_count
    j = num - i + 1
else:
    i = num - (x - num_count) + 1
    j = x - num_count

print(f"{i}/{j}")

코드가 조금 난해해서 다른사람들에게 설명하기 어려울 것 같지만 해보자면

 

우리는 이 나열되는 수들의 규칙을 발견했기 때문에 굳이 시간초과를 감수하면서

 

1부터 시작할 필요가 없다.

 

예제에 나오는 14를 예를 들어보자면

 

14는 (1 + 2+ 3+ 4) < 14 < (1 + 2 + 3 + 4 + 5) 사이에 있는 수이다.

 

그렇다면 우리는 굳이 i와 j를 num_count가 10번째가 되기 이전에 계속 바꿀 필요가 없다는 뜻이다.

 

x = 14일 때 첫 번째 while문이 종료될 때 num_count = 15, num = 5이다.

 

그래서 num_count에서 num만큼 빼준후에 거기서부터 i와 j를 찾아주면 되는것이다.

 

이 때, num이 홀수이기 때문에 앞서 말했던 규칙을 따르면

 

홀수씩 늘어날 때는 분자는 n부터 1까지 줄어들고 분모는 1부터 n까지 늘어난다.

 

그래서 홀수일 때는 i와 j를 이런식으로 나타낼 수 있는 것이다.

i = num - (x - num_count) + 1
j = x - num_count

아까 예를들던 14를 계속해서 풀어보자면

 

i = num(5) - (x(14) - num_count(10)) + 1 = 2

j = x(14) - num_count(10) = 4

 

따라서 출력값으로 2/4가 나올 수 있는 것이다.

 

이런식으로 i와 j를 구한다음에 출력해주면 되고 출력할 때는

 

f-string을 사용하여서 출력해주었다.